시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB381483214.953%

문제

학생들은 스타 대회를 열기로 했다. 참가자는 총 N명으로 1번부터 N번까지 번호가 붙어있다. 토너먼트의 규칙은 다음과 같다. 게임이 진행되는 동안 남아있는 참가자 중 임의의 두 명을 뽑아 스타를 붙인다. 경기 후 패자는 탈락되고 승자는 계속해서 대회에 참가하게 된다. (단, 무승부는 존재하지 않는다.) 결국 N-1번의 게임을 하면 최후의 승자가 남게 되고 이 학생이 우승을 하게 된다.


참가자 중 어떤 한 학생이 다른 한 학생을 항상 이기는 천적 관계가 존재한다. 즉, 이 두 학생끼리는 경기를 펼치지 않아도 누가 이긴다는 것을 알 수 있다는 것이다. 예를 들어, 위와 같은 그래프에서 1번은 2, 3번을 항상 이긴다는 뜻이다. 하지만 1번과 4번이 경기하면 1번이 이길 수도 있고 4번이 이길 수도 있다.

N명의 참가자에 대한 천적 관계가 주어졌을 때 우승 가능성이 있는 학생들을 알 수 있다. 예를 들어, 위의 예에서 3번 학생은 1번 학생한테 항상 지지만 4번 학생과 1번 학생이 경기를 하여 1번 학생이 탈락한 후 3번 학생이 2, 4번 학생을 차례대로 이기고 우승할 수 있기 때문에 우승 가능성이 있는 학생이다.

문제는 N명의 참가자에 대한 천적 관계가 주어지면 우승 가능성이 있는 학생들을 모두 구하는 것이다.

입력

첫째 줄에 참가자 수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에 천적관계가 주어지는데 i+1번째 줄에는 i번째 학생이 항상 이기는 학생의 수 와 이 학생들의 번호가 공백으로 구분되어 증가하는 순서로 주어진다. (단, 자기 자신이 천적인 경우는 없다.) 천적 관계의 총 수는 1,000,000을 넘지 않는다.

출력

첫째 줄에 우승 가능성이 있는 학생 수 w와 이 학생들의 번호를 오름차순으로 공백으로 구분하여 출력한다.

예제 입력 1

4
2 2 3
0
1 2
1 2

예제 출력 1

3 1 3 4
W3sicHJvYmxlbV9pZCI6IjE2MDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYTRcdWQwYzAgXHViMzAwXHVkNjhjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHVjMmE0XHVkMGMwIFx1YjMwMFx1ZDY4Y1x1Yjk3YyBcdWM1ZjRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWNjMzhcdWFjMDBcdWM3OTBcdWIyOTQgXHVjZDFkIE5cdWJhODVcdWM3M2NcdWI4NWMgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1YjRcdWM3ODhcdWIyZTQuIFx1ZDFhMFx1YjEwOFx1YmEzY1x1ZDJiOFx1Yzc1OCBcdWFkZGNcdWNlNTlcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNzc0IFx1YzljNFx1ZDU4OVx1YjQxOFx1YjI5NCBcdWIzZDlcdWM1NDggXHViMGE4XHVjNTQ0XHVjNzg4XHViMjk0IFx1Y2MzOFx1YWMwMFx1Yzc5MCBcdWM5MTEgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YjQ1MCBcdWJhODVcdWM3NDQgXHViZjUxXHVjNTQ0IFx1YzJhNFx1ZDBjMFx1Yjk3YyBcdWJkOTlcdWM3NzhcdWIyZTQuIFx1YWNiZFx1YWUzMCBcdWQ2YzQgXHVkMzI4XHVjNzkwXHViMjk0IFx1ZDBjOFx1Yjc3ZFx1YjQxOFx1YWNlMCBcdWMyYjlcdWM3OTBcdWIyOTQgXHVhY2M0XHVjMThkXHVkNTc0XHVjMTFjIFx1YjMwMFx1ZDY4Y1x1YzVkMCBcdWNjMzhcdWFjMDBcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiAoXHViMmU4LCBcdWJiMzRcdWMyYjlcdWJkODBcdWIyOTQgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4pIFx1YWNiMFx1YWQ2ZCBOLTFcdWJjODhcdWM3NTggXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YmE3NCBcdWNkNWNcdWQ2YzRcdWM3NTggXHVjMmI5XHVjNzkwXHVhYzAwIFx1YjBhOFx1YWM4YyBcdWI0MThcdWFjZTAgXHVjNzc0IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWM2YjBcdWMyYjlcdWM3NDQgXHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG48cD48YnIgXC8+XHJcbjxpbWcgd2lkdGg9XCIxMzNcIiBoZWlnaHQ9XCIxNzFcIiBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvMjAxMDA0XC9zdGFyLnBuZ1wiIFwvPjxcL3A+XHJcbjxwPlx1Y2MzOFx1YWMwMFx1Yzc5MCBcdWM5MTEgXHVjNWI0XHViNWE0IFx1ZDU1YyBcdWQ1NTlcdWMwZGRcdWM3NzQgXHViMmU0XHViOTc4IFx1ZDU1YyBcdWQ1NTlcdWMwZGRcdWM3NDQgXHVkNTZkXHVjMGMxIFx1Yzc3NFx1YWUzMFx1YjI5NCBcdWNjOWNcdWM4MDEgXHVhZDAwXHVhY2M0XHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWM3NzQgXHViNDUwIFx1ZDU1OVx1YzBkZFx1YjA3Y1x1YjlhY1x1YjI5NCBcdWFjYmRcdWFlMzBcdWI5N2MgXHVkM2JjXHVjZTU4XHVjOWMwIFx1YzU0YVx1YzU0NFx1YjNjNCBcdWIyMDRcdWFjMDAgXHVjNzc0XHVhZTM0XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM1NGMgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhZGY4XHViNzk4XHVkNTA0XHVjNWQwXHVjMTFjIDFcdWJjODhcdWM3NDAgMiwgM1x1YmM4OFx1Yzc0NCBcdWQ1NmRcdWMwYzEgXHVjNzc0XHVhZTM0XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIDFcdWJjODhcdWFjZmMgNFx1YmM4OFx1Yzc3NCBcdWFjYmRcdWFlMzBcdWQ1NThcdWJhNzQgMVx1YmM4OFx1Yzc3NCBcdWM3NzRcdWFlMzggXHVjMjE4XHViM2M0IFx1Yzc4OFx1YWNlMCA0XHViYzg4XHVjNzc0IFx1Yzc3NFx1YWUzOCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbjxwPk5cdWJhODVcdWM3NTggXHVjYzM4XHVhYzAwXHVjNzkwXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWNjOWNcdWM4MDEgXHVhZDAwXHVhY2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMgXHVjNmIwXHVjMmI5IFx1YWMwMFx1YjJhNVx1YzEzMVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQ0IFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM3MDRcdWM3NTggXHVjNjA4XHVjNWQwXHVjMTFjIDNcdWJjODggXHVkNTU5XHVjMGRkXHVjNzQwIDFcdWJjODggXHVkNTU5XHVjMGRkXHVkNTVjXHVkMTRjIFx1ZDU2ZFx1YzBjMSBcdWM5YzBcdWM5YzBcdWI5Y2MgNFx1YmM4OCBcdWQ1NTlcdWMwZGRcdWFjZmMgMVx1YmM4OCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVhY2JkXHVhZTMwXHViOTdjIFx1ZDU1OFx1YzVlYyAxXHViYzg4IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWQwYzhcdWI3N2RcdWQ1NWMgXHVkNmM0IDNcdWJjODggXHVkNTU5XHVjMGRkXHVjNzc0IDIsIDRcdWJjODggXHVkNTU5XHVjMGRkXHVjNzQ0IFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWM3NzRcdWFlMzBcdWFjZTAgXHVjNmIwXHVjMmI5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzZiMFx1YzJiOSBcdWFjMDBcdWIyYTVcdWMxMzFcdWM3NzQgXHVjNzg4XHViMjk0IFx1ZDU1OVx1YzBkZFx1Yzc3NFx1YjJlNC48XC9wPlxyXG48cD5cdWJiMzhcdWM4MWNcdWIyOTQgTlx1YmE4NVx1Yzc1OCBcdWNjMzhcdWFjMDBcdWM3OTBcdWM1ZDAgXHViMzAwXHVkNTVjIFx1Y2M5Y1x1YzgwMSBcdWFkMDBcdWFjYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTc0IFx1YzZiMFx1YzJiOSBcdWFjMDBcdWIyYTVcdWMxMzFcdWM3NzQgXHVjNzg4XHViMjk0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0NCBcdWJhYThcdWI0NTAgXHVhZDZjXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjYzM4XHVhYzAwXHVjNzkwIFx1YzIxOCBOKDEmbGU7TiZsZTsxMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWNjOWNcdWM4MDFcdWFkMDBcdWFjYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwIGkrMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgaVx1YmM4OFx1YzlmOCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVkNTZkXHVjMGMxIFx1Yzc3NFx1YWUzMFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NTggXHVjMjE4IFx1YzY0MCBcdWM3NzQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoXHViMmU4LCBcdWM3OTBcdWFlMzAgXHVjNzkwXHVjMmUwXHVjNzc0IFx1Y2M5Y1x1YzgwMVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LikgXHVjYzljXHVjODAxIFx1YWQwMFx1YWNjNFx1Yzc1OCBcdWNkMWQgXHVjMjE4XHViMjk0IDEsMDAwLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+Iiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM2YjBcdWMyYjkgXHVhYzAwXHViMmE1XHVjMTMxXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWQ1NTlcdWMwZGQgXHVjMjE4IHdcdWM2NDAgXHVjNzc0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTYwOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRoZSBUb3VybmFtZW50IiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgSW50ZXJuYXRpb25hbCBYLUdhbWUgRmVkZXJhdGlvbiBvcmdhbmlzZXMgYSB0b3VybmFtZW50IGluIHdoaWNoIHByb2dyYW1tZXMgdGhhdCBwbGF5IHRoaXMgZ2FtZSBwYXJ0aWNpcGF0ZS4gJm5ic3A7cHJvZ3JhbW1lcyBudW1iZXJlZCBmcm9tICZuYnNwO3RvICZuYnNwO3Rha2UgcGFydCBpbiB0aGUgY29tcGV0aXRpb24uIFRoZSBydWxlcyBvZiB0aGUgdG91cm5hbWVudCBhcmUgYXMgZm9sbG93czogd2hpbGUgdGhlcmUgcmVtYWlucyBtb3JlIHRoYW4gb25lIHByb2dyYW1tZSBpbiB0aGUgdG91cm5hbWVudCwgdHdvIG9mIHRoZW0gKGRpc3RpbmN0KSBhcmUgcmFuZG9tbHkgY2hvc2VuIHRvIHBsYXkgYSBnYW1lLiBUaGUgZGVmZWF0ZWQgb25lICh0aGVyZSBhcmUgbm8gZHJhd3MgaW4gdGhlIFgtR2FtZSkgZHJvcHMgb3V0IG9mIHRoZSB0b3VybmFtZW50IGFuZCB0aGUgd2hvbGUgcHJvY2VkdXJlIGlzIHJlcGVhdGVkLiBUaGUgc29sZSBwcm9ncmFtbWUgd2hpY2ggc3RheXMgaW4gdGhlIHRvdXJuYW1lbnQgYWZ0ZXIgYWxsICZuYnNwO2dhbWVzIGhhdmUgYmVlbiBwbGF5ZWQgaXMgdGhlIHdpbm5lci48XC9wPlxyXG5cclxuPHA+VGhlIGZlZGVyYXRpb24gaGFzIGEgdGFibGUgb2YgcmVzdWx0cyBvZiBwcmV2aW91cyB0b3VybmFtZW50cy4gSXQgaXMga25vd24sIHRoYXQgdGhlIHByb2dyYW1tZXMgcGxheSBkZXRlcm1pbmlzdGljYWxseSAoaS5lLiBpbiByZXBlYXRhYmxlIGZhc2hpb24pIGFuZCBpbiBleGFjdGx5IHRoZSBzYW1lIHdheSBhcyBpbiBwcmV2aW91cyB0b3VybmFtZW50cy4gU28sIGlmIHR3byBwcm9ncmFtbWVzIGhhdmUgYWxyZWFkeSBwbGF5ZWQgb25lIGFnYWluc3QgYW5vdGhlciB0aGVuIHRoZWlyIG5leHQgZ2FtZSB3aWxsIGVuZCB3aXRoIHRoZSBzYW1lIHJlc3VsdC4gSWYsIGhvd2V2ZXIsIHRoZXkgaGF2ZSBuZXZlciBwbGF5ZWQgYWdhaW5zdCBlYWNoIG90aGVyLCB0aGUgb3V0Y29tZSBvZiB0aGUgZ2FtZSBjYW5ub3QgYmUgcHJlZGljdGVkIC0gYm90aCBoYXZlIGEgY2hhbmNlIG9mIHdpbm5pbmcuIFRoZSBmZWRlcmF0aW9uIHdvdWxkIGxpa2UgdG8ga25vdyBhIGxpc3Qgb2YgYWxsIHByb2dyYW1tZXMgd2hpY2ggaGF2ZSBhIGNoYW5jZSBvZiB3aW5uaW5nIHRoZSB0b3VybmFtZW50LjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW1tZSB3aGljaDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCB0aGUgbnVtYmVyIG9mIHBhcnRpY2lwYXRpbmcgcHJvZ3JhbW1lcyBhbmQgdGhlIHRhYmxlIG9mIHJlc3VsdHMgb2YgdGhlaXIgcHJldmlvdXMgZ2FtZXMsPFwvbGk+XHJcblx0PGxpPmRldGVybWluZXMgYWxsIHByb2dyYW1tZXMgd2hpY2ggaGF2ZSBhIGNoYW5jZSBvZiB3aW5uaW5nIHRoZSB0b3VybmFtZW50LDxcL2xpPlxyXG5cdDxsaT53cml0ZXMgdGhlIG91dGNvbWUgdG8gdGhlIHN0YW5kYXJkIG91dHB1dC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgbiwgMSAmbGU7IG4gJmxlOyAxMDAgMDAwLiBUaGUgbmV4dCBuIGxpbmVzIGNvbnRhaW4gdGhlIHRhYmxlIG9mIHJlc3VsdHMgb2YgcHJldmlvdXMgZ2FtZXM6IChpKzEpc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIGtpLCAwICZsZTsga2kgJmxlOyBuLCBmb2xsb3dlZCBieSBraSBudW1iZXJzIG9mIHByb2dyYW1tZXMsIG5vdCBlcXVhbCB0byBpLCBpbiBpbmNyZWFzaW5nIG9yZGVyIC0gdGhvc2UgYXJlIHRoZSBudW1iZXJzIG9mIHByb2dyYW1tZXMsIHdpdGggd2hpY2ggdGhlIHByb2dyYW1tZSBpIGhhcyBwcmV2aW91c2x5IHdvbi4gVGhlIG51bWJlcnMgaW4gbGluZXMgYXJlIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLiBUaGUgbnVtYmVyIG9mIGFsbCBrbm93biByZXN1bHRzIG9mIHByZXZpb3VzIGdhbWVzIGRvZXMgbm90IGV4Y2VlZCAxIDAwMCAwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgdGhlIHN0YW5kYXJkIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVyIHcgb2YgcHJvZ3JhbW1lcyB3aGljaCBoYXZlIGEgY2hhbmNlIG9mIHdpbm5pbmcgdGhlIHRvdXJuYW1lbnQsIGZvbGxvd2VkIGJ5IHcgbnVtYmVycyBpZGVudGlmeWluZyB0aG9zZSBwcm9ncmFtbWVzLCBpbiBpbmNyZWFzaW5nIG9yZGVyLiBUaGUgbnVtYmVycyBzaG91bGQgYmUgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMDA3XC9ycnIuUE5HXCIgc3R5bGU9XCJoZWlnaHQ6MTYwcHg7IHdpZHRoOjEyNHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > Polish Olympiad in Informatics > POI 2003/2004 > Stage 2 5번

  • 문제를 번역한 사람: author6