1170: 控制公司

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:7 通过:6

题目描述

满足下面三个条件之一,公司A可以控制公司B:

  • 公司A=公司B
  • 公司A拥有超过50%的公司B的股票
  • 公司A控制K个公司,记为C1,C2,...,CK,每个被控制的公司加起来拥有超过50%的公司B的股票

给你N个信息,包含所有公司之间的股票关系,输出所有二元组<x,y>,表示公司x控制公司y。

不超过100个公司。

输入格式

第一行为正整数N,N不超过3000。
接下来N行,每行三个整数i,j,k,表示i公司拥有j公司p%的股份。

输出格式

输出若干行,每行两个整数x和y,表示x公司控制了y公司。
不要输出x=y的情况。
按照x为第一关键字、y为第二关键字升序输出。

输入样例 复制

3
1 2 80
2 3 80
3 1 20

输出样例 复制

1 2
1 3
2 3