어떤 회사가 다른 회사의 주식을 일부 갖고 있다면 주식을 가진 회사는 그 회사를 부분적으로 소유하고 있다고 말한다.

예를 들어 포드 사는 마쓰다 사를 12 % 소유하고 하고 있다. 그리고 다음 세 조건 중 하나라도 만족하는 회사 A,B 가 있으면 회사 A 가 회사 B 를 지배한다고 말한다.

• A=B
• A 가 B 를 50 % 이상 소유한다.
• 이미 A 의 지배를 받고 있는 다른 회사들이 B 를 지배한다고 말한다.

"i 라는 회사가 j 라는 회사를 p % 소유하고 있다" 를 뜻하는 세수 (i,j,p)의 목록을 읽어 이들을 총 분석한 뒤" 회사 h 가 회사 회사 s 를 지배하고 있다"를 뜻하는 숫자쌍 (h,s) 를 계산, 출력하는 프로그램을 작성하라. 회사는 최대 100 개까지 있다.

다음과 같은 처리를 하는 프로그램을 작성하라.

1. 입력에서 (i,j,p) 의 값을 읽는다. 세 숫자는 한 줄에 한 개씩 들어있으며 , 모두 양수이다. 입력에 따로 처리할 입력 자료가 여러개 있으며, 이들은 빈 줄로 구분한다.
2. 지배하는 회사(h)와 지배당하는 회사의 짝(s)을 모두 찾아낸다.
3. 찾은 (h,s)쌍을 모두 기록한다. h 와 s 는 서로 다른 수치이여야 하며 , h 를 기준으로 오름차순으로 정렬하여 출력하도록 한다. 다른 입력으로 넘어가서 답을 출력한다면 빈 줄로 각 자료를 구분한다.

입력과 출력의 예

입력

2 3 25
1 4 36
4 5 63
2 1 48
3 4 30
4 2 52
5 3 30

출력

4 2
4 3
4 5

입력

1 2 30
2 3 52
3 4 51
4 5 70
5 4 20
4 3 20

출력

2 3
2 4
2 5
3 4
3 5
4 5

출처: ioi 기출