Description

Some companies are partial owners of other companies because they own a portion of the shares issued by those companies.

It is said that if at least one of the following three conditions is met, company $A$ can control company $B$:

• Company $A$ = company $B$.
• Company $A$ owns more than $50\%$ of company $B$'s stock.
• Company $A$ controls $K$ ($K \geq 1$) companies, denoted $C_1, \ldots, C_K$, each company $C_i$ owns $x_i\%$ of company $B$'s stock, and $x_1+ \ldots + x_K \gt 50\%$.

You are given a table where each row contains three numbers $i,j,p$: it means company $i$ owns $p\%$ of company $j$. Compute all pairs $(h,s)$ indicating that company $h$ controls company $s$. There are at most $100$ companies.

Input Format

The first line contains an integer $N$, the number of rows in the table.

Each of the next $N$ lines contains three integers $i,j,p$, meaning company $i$ owns $p\%$ of company $j$'s stock.

Output Format

Output zero or more companies that control other companies. Each line contains two integers $A,B$, meaning company $A$ controls company $B$. Sort the output pairs in ascending order by $A$ as the primary key and $B$ as the secondary key.

Do not output cases where a company controls itself (i.e., all pairs must satisfy $A \neq B$).

3
1 2 80
2 3 80
3 1 20

1 2
1 3
2 3

Hint

Translated from NOCOW.

USACO 2.3.

Translated by ChatGPT 5