백준 온라인 저지, 분리집합 / 20040번: 사이클게임 (파이썬 / 백준 골드문제)

문제

사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다. 사이클 C는 플레이어가 그린 선분들의 부분집합으로, 다음 조건을 만족한다.

C에 속한 임의의 선분의 한 끝점에서 출발하여 모든 선분을 한 번씩만 지나서 출발점으로 되돌아올 수 있다.

문제는 선분을 여러 개 그리다 보면 사이클이 완성 되었는지의 여부를 판단하기 어려워 이미 사이클이 완성되었음에도 불구하고 게임을 계속 진행하게 될 수 있다는 것이다. 이 문제를 해결하기 위해서 게임의 진행 상황이 주어지면 몇 번째 차례에서 사이클이 완성되었는지, 혹은 아직 게임이 진행 중인지를 판단하는 프로그램을 작성하려 한다.

입력으로 점의 개수 n과 m 번째 차례까지의 게임 진행 상황이 주어지면 사이클이 완성 되었는지를 판단하고, 완성되었다면 몇 번째 차례에서 처음으로 사이클이 완성된 것인지를 출력하는 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 입력의 첫 번째 줄에는 점의 개수를 나타내는 정수 3 ≤ n ≤ 500,000 과 진행된 차례의 수를 나타내는 정수 3 ≤ m ≤ 1,000,000 이 주어진다. 게임에서 사용하는 n개의 점에는 0 부터 n − 1 까지 고유한 번호가 부여되어 있으며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 이어지는 m 개의 입력 줄에는 각각 i번째 차례에 해당 플레이어가 선택한 두 점의 번호가 주어진다 (1 ≤ i ≤ m).

출력

출력은 표준출력을 사용한다. 입력으로 주어진 케이스에 대해, m 번째 차례까지 게임을 진행한 상황에서 이미 게임이 종료되었다면 사이클이 처음으로 만들어진 차례의 번호를 양의 정수로 출력하고, m 번의 차례를 모두 처리한 이후에도 종료되지 않았다면 0을 출력한다.

제한

예제 입력 1

6 5
0 1
1 2
2 3
5 4
0 4

예제 출력 1

0

예제 입력 2

6 5
0 1
1 2
1 3
0 3
4 5

예제 출력 2

4

힌트

W3sicHJvYmxlbV9pZCI6IjIwMDQwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMGFjXHVjNzc0XHVkMDc0IFx1YWM4Y1x1Yzc4NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGFjXHVjNzc0XHVkMDc0IFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWI0NTAgXHViYTg1XHVjNzU4IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHViM2NjXHVjNTQ0XHVhYzAwXHViYTcwIFx1YzljNFx1ZDU4OVx1ZDU1OFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3M2NcdWI4NWMsIFx1YzEyMCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHVkNjQwXHVjMjE4IFx1YmM4OFx1YzlmOCBcdWNjMjhcdWI4NDBcdWI5N2MsIFx1ZDZjNCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHVjOWRkXHVjMjE4IFx1YmM4OFx1YzlmOCBcdWNjMjhcdWI4NDBcdWI5N2MgXHVjOWM0XHVkNTg5XHVkNTVjXHViMmU0LiBcdWFjOGNcdWM3ODQgXHVjMmRjXHVjNzkxIFx1YzJkYyAwIFx1YmQ4MFx1ZDEzMCA8ZW0+bjxcL2VtPiAmbWludXM7IDEgXHVhZTRjXHVjOWMwIFx1YWNlMFx1YzcyMFx1ZDU1YyBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDgwXHVjNWVjXHViNDFjIFx1ZDNjOVx1YmE3NCBcdWMwYzFcdWM3NTggXHVjODEwIDxlbT5uPFwvZW0+IFx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1Yzc3NCBcdWM5MTEgXHVjNWI0XHViMjkwIFx1YzEzOCBcdWM4MTBcdWIzYzQgXHVjNzdjXHVjOWMxXHVjMTIwIFx1YzcwNFx1YzVkMCBcdWIxOTNcdWM3NzRcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWI5ZTQgXHVjYzI4XHViODQwIFx1YjljOFx1YjJlNCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWIyOTQgXHViNDUwIFx1YzgxMFx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NzRcdWMxMWMgXHVjNzc0XHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWMxMjBcdWJkODRcdWM3NDQgXHVhZTBiXHViMjk0XHViMzcwLCBcdWM3NzRcdWM4MDRcdWM1ZDAgXHVhZGY4XHViOWIwIFx1YzEyMFx1YmQ4NFx1Yzc0NCBcdWIyZTRcdWMyZGMgXHVhZGY4XHVjNzQ0IFx1YzIxOFx1YjI5NCBcdWM1YzZcdWM5YzBcdWI5Y2MgXHVjNzc0XHViYmY4IFx1YWRmOFx1YjliMCBcdWIyZTRcdWI5NzggXHVjMTIwXHViZDg0XHVhY2ZjIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LiBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjOWM0XHVkNTg5XHVkNTU4XHViMmU0XHVhYzAwIFx1Y2M5OFx1Yzc0Y1x1YzczY1x1Yjg1YyBcdWMwYWNcdWM3NzRcdWQwNzRcdWM3NDQgXHVjNjQ0XHVjMTMxXHVkNTU4XHViMjk0IFx1YzIxY1x1YWMwNCBcdWFjOGNcdWM3ODRcdWM3NzQgXHVjODg1XHViOGNjXHViNDFjXHViMmU0LiBcdWMwYWNcdWM3NzRcdWQwNzQgPGVtPkM8XC9lbT5cdWIyOTQgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIFx1YWRmOFx1YjliMCBcdWMxMjBcdWJkODRcdWI0ZTRcdWM3NTggXHViZDgwXHViZDg0XHVjOWQxXHVkNTY5XHVjNzNjXHViODVjLCBcdWIyZTRcdWM3NGMgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPGJsb2NrcXVvdGU+XHJcbjxwPjxlbT5DPFwvZW0+XHVjNWQwIFx1YzE4ZFx1ZDU1YyBcdWM3ODRcdWM3NThcdWM3NTggXHVjMTIwXHViZDg0XHVjNzU4IFx1ZDU1YyBcdWIwNWRcdWM4MTBcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTU4XHVjNWVjIFx1YmFhOFx1YjRlMCBcdWMxMjBcdWJkODRcdWM3NDQgXHVkNTVjIFx1YmM4OFx1YzUyOVx1YjljYyBcdWM5YzBcdWIwOThcdWMxMWMgXHVjZDljXHViYzFjXHVjODEwXHVjNzNjXHViODVjIFx1YjQxOFx1YjNjY1x1YzU0NFx1YzYyYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbjxcL2Jsb2NrcXVvdGU+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWIyOTQgXHVjMTIwXHViZDg0XHVjNzQ0IFx1YzVlY1x1YjdlYyBcdWFjMWMgXHVhZGY4XHViOWFjXHViMmU0IFx1YmNmNFx1YmE3NCBcdWMwYWNcdWM3NzRcdWQwNzRcdWM3NzQgXHVjNjQ0XHVjMTMxIFx1YjQxOFx1YzVjOFx1YjI5NFx1YzljMFx1Yzc1OCBcdWM1ZWNcdWJkODBcdWI5N2MgXHVkMzEwXHViMmU4XHVkNTU4XHVhZTMwIFx1YzViNFx1YjgyNFx1YzZjYyBcdWM3NzRcdWJiZjggXHVjMGFjXHVjNzc0XHVkMDc0XHVjNzc0IFx1YzY0NFx1YzEzMVx1YjQxOFx1YzVjOFx1Yzc0Y1x1YzVkMFx1YjNjNCBcdWJkODhcdWFkNmNcdWQ1NThcdWFjZTAgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YWNjNFx1YzE4ZCBcdWM5YzRcdWQ1ODlcdWQ1NThcdWFjOGMgXHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM3NzQgXHViYjM4XHVjODFjXHViOTdjIFx1ZDU3NFx1YWNiMFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVhYzhjXHVjNzg0XHVjNzU4IFx1YzljNFx1ZDU4OSBcdWMwYzFcdWQ2NjlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTc0IFx1YmE4NyBcdWJjODhcdWM5ZjggXHVjYzI4XHViODQwXHVjNWQwXHVjMTFjIFx1YzBhY1x1Yzc3NFx1ZDA3NFx1Yzc3NCBcdWM2NDRcdWMxMzFcdWI0MThcdWM1YzhcdWIyOTRcdWM5YzAsIFx1ZDYzOVx1Yzc0MCBcdWM1NDRcdWM5YzEgXHVhYzhjXHVjNzg0XHVjNzc0IFx1YzljNFx1ZDU4OSBcdWM5MTFcdWM3NzhcdWM5YzBcdWI5N2MgXHVkMzEwXHViMmU4XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCA8ZW0+bjxcL2VtPlx1YWNmYyA8ZW0+bTxcL2VtPiBcdWJjODhcdWM5ZjggXHVjYzI4XHViODQwXHVhZTRjXHVjOWMwXHVjNzU4IFx1YWM4Y1x1Yzc4NCBcdWM5YzRcdWQ1ODkgXHVjMGMxXHVkNjY5XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCBcdWMwYWNcdWM3NzRcdWQwNzRcdWM3NzQgXHVjNjQ0XHVjMTMxIFx1YjQxOFx1YzVjOFx1YjI5NFx1YzljMFx1Yjk3YyBcdWQzMTBcdWIyZThcdWQ1NThcdWFjZTAsIFx1YzY0NFx1YzEzMVx1YjQxOFx1YzVjOFx1YjJlNFx1YmE3NCBcdWJhODcgXHViYzg4XHVjOWY4IFx1Y2MyOFx1Yjg0MFx1YzVkMFx1YzExYyBcdWNjOThcdWM3NGNcdWM3M2NcdWI4NWMgXHVjMGFjXHVjNzc0XHVkMDc0XHVjNzc0IFx1YzY0NFx1YzEzMVx1YjQxYyBcdWFjODNcdWM3NzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVkNDVjXHVjOTAwXHVjNzg1XHViODI1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCAzICZsZTsgPGVtPm48XC9lbT4gJmxlOyA1MDAsMDAwIFx1YWNmYyBcdWM5YzRcdWQ1ODlcdWI0MWMgXHVjYzI4XHViODQwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4IDMgJmxlOyA8ZW0+bTxcL2VtPiAmbGU7IDEsMDAwLDAwMCBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjOGNcdWM3ODRcdWM1ZDBcdWMxMWMgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IDxlbT5uPFwvZW0+XHVhYzFjXHVjNzU4IFx1YzgxMFx1YzVkMFx1YjI5NCAwIFx1YmQ4MFx1ZDEzMCA8ZW0+bjxcL2VtPiAmbWludXM7IDEgXHVhZTRjXHVjOWMwIFx1YWNlMFx1YzcyMFx1ZDU1YyBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDgwXHVjNWVjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjNzc0IFx1YzkxMSBcdWM1YjRcdWIyOTAgXHVjMTM4IFx1YzgxMFx1YjNjNCBcdWM3N2NcdWM5YzFcdWMxMjAgXHVjNzA0XHVjNWQwIFx1YjE5M1x1Yzc3NFx1YzljMCZuYnNwO1x1YzU0YVx1YjI5NFx1YjJlNC4gXHVjNzc0XHVjNWI0XHVjOWMwXHViMjk0IDxlbT5tPFwvZW0+IFx1YWMxY1x1Yzc1OCBcdWM3ODVcdWI4MjUgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMSA8ZW0+aTxcL2VtPlx1YmM4OFx1YzlmOCBcdWNjMjhcdWI4NDBcdWM1ZDAgXHVkNTc0XHViMmY5IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWMxMjBcdWQwZGRcdWQ1NWMgXHViNDUwIFx1YzgxMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0ICgxICZsZTsgPGVtPmk8XC9lbT4gJmxlOyA8ZW0+bTxcL2VtPikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFx1ZDQ1Y1x1YzkwMFx1Y2Q5Y1x1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCwgPGVtPm08XC9lbT4gXHViYzg4XHVjOWY4IFx1Y2MyOFx1Yjg0MFx1YWU0Y1x1YzljMCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjOWM0XHVkNTg5XHVkNTVjIFx1YzBjMVx1ZDY2OVx1YzVkMFx1YzExYyBcdWM3NzRcdWJiZjggXHVhYzhjXHVjNzg0XHVjNzc0IFx1Yzg4NVx1YjhjY1x1YjQxOFx1YzVjOFx1YjJlNFx1YmE3NCBcdWMwYWNcdWM3NzRcdWQwNzRcdWM3NzQgXHVjYzk4XHVjNzRjXHVjNzNjXHViODVjIFx1YjljY1x1YjRlNFx1YzViNFx1YzljNCBcdWNjMjhcdWI4NDBcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCA8ZW0+bTxcL2VtPiBcdWJjODhcdWM3NTggXHVjYzI4XHViODQwXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWNjOThcdWI5YWNcdWQ1NWMgXHVjNzc0XHVkNmM0XHVjNWQwXHViM2M0IFx1Yzg4NVx1YjhjY1x1YjQxOFx1YzljMCBcdWM1NGFcdWM1NThcdWIyZTRcdWJhNzQgMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjAwNDAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDeWNsZSBHYW1lIiwiZGVzY3JpcHRpb24iOiI8cD5DeWNsZSBnYW1lIGlzIGEgZ2FtZSBpbiB3aGljaCB0d28gcGxheWVycyB0YWtlIHR1cm5zIGRyYXdpbmcgYSBsaW5lIHNlZ21lbnQgZm9yIGdpdmVuIHBvaW50cy4gVGhlIGZpcnN0IHBsYXllciBnZXRzIHRvIGRyYXcgYSBsaW5lIHNlZ21lbnQgaW4gdGhlIG9kZC1udW1iZXJlZCB0dXJucywgd2hpbGUgdGhlIG90aGVyIHBsYXllciB0YWtlcyBldmVuLW51bWJlcmVkIHR1cm5zLiBBdCB0aGUgc3RhcnQgb2YgdGhlIGdhbWUsIDxlbT5uPFwvZW0+IHBvaW50cyBhcmUgZ2l2ZW4gaW4gdGhlIHBsYW5lLCBhbmQgZWFjaCBvZiB0aGUgcG9pbnRzIGhhcyBhIHVuaXF1ZSBudW1iZXIgZnJvbSAwIHRvIDxlbT5uPFwvZW0+ICZtaW51czsgMS4gTm90ZSB0aGF0IG5vIHRocmVlIHBvaW50cyBsaWUgb24gYSBzYW1lIGxpbmUuIEluIGVhY2ggdHVybiwgYSBwbGF5ZXIgZHJhd3MgYSBsaW5lIHNlZ21lbnQgY29ubmVjdGluZyB0d28gZ2l2ZW4gcG9pbnRzLiBQbGF5ZXJzIGNhbm5vdCByZWRyYXcgYSBsaW5lIHNlZ21lbnQgd2hpY2ggaGFzIGFscmVhZHkgYmVlbiBkcmF3biwgYnV0IGl0IGlzIGFsbG93ZWQgdG8gZHJhdyBhIGxpbmUgc2VnbWVudCBhY3Jvc3MgZXhpc3RpbmcgbGluZSBzZWdtZW50cy4gUGxheWVycyB0YWtlIHR1cm5zIHVudGlsIHRoZXJlIGlzIHRoZSBsb3NlciB3aG8gY29tcGxldGVzIGEgY3ljbGUgZmlyc3QuIEEgY3ljbGUgPGVtPkM8XC9lbT4gaXMgYSBzdWJzZXQgb2YgdGhlIGxpbmUgc2VnbWVudHMgZHJhd24gYnkgdGhlIHBsYXllcnMgd2hpY2ggc2F0aXNmaWVzIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9uLjxcL3A+XHJcblxyXG48YmxvY2txdW90ZT5cclxuPHA+RnJvbSBhbnkgZW5kcG9pbnQgb2YgYSBsaW5lIHNlZ21lbnQgaW4gPGVtPkM8XC9lbT4sIG9uZSBjYW4gdHJhdmVsIGRvd24gYW5kIHJldHVybiB0byB0aGUgZW5kIHBvaW50IHdoaWxlIHZpc2l0aW5nIGV2ZXJ5IGxpbmUgc2VnbWVudCBpbiA8ZW0+QzxcL2VtPiBleGFjdGx5IG9uY2UuPFwvcD5cclxuPFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPkEgcHJvYmxlbSBpcyB0aGF0IGFzIHBsYXllcnMgZHJhdyBtYW55IHNlZ21lbnRzLCBpdCBpcyBkaWZmaWN1bHQgdG8gY2hlY2sgd2hldGhlciBhIGN5Y2xlIGlzIGNyZWF0ZWQuIFRoZXJlZm9yZSwgc29tZXRpbWVzIHBsYXllcnMgY29udGludWUgdG8gcGxheSB0aGUgZ2FtZSBldmVuIHRob3VnaCBhIGN5Y2xlIGhhcyBiZWVuIG1hZGUgYW5kIHRoZSBnYW1lIGlzIGFjdHVhbGx5IG92ZXIuIFRvIHByZXZlbnQgdGhpcyBzaXR1YXRpb24sIHdlIG5lZWQgdG8gd3JpdGUgYSBwcm9ncmFtIHdoaWNoIGV4YW1pbmVzIHdoZXRoZXIgdGhlIGdhbWUgaGFzIGJlZW4gb3Zlci48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRvIGRlY2lkZSB3aGV0aGVyIHRoZSBnYW1lIGhhcyBiZWVuIG92ZXIgYW5kIG91dHB1dCBpbiB3aGljaCB0dXJuIHRoZSBmaXJzdCBjeWNsZSBoYXMgYmVlbiBtYWRlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIHR3byBpbnRlZ2VycyAzICZsZTsgPGVtPm48XC9lbT4gJmxlOyA1MDAsMDAwIGFuZCAzICZsZTsgPGVtPm08XC9lbT4gJmxlOyAxLDAwMCwwMDAsIHdoZXJlIDxlbT5uPFwvZW0+IHJlcHJlc2VudHMgdGhlIG51bWJlciBvZiBwb2ludHMgYW5kIDxlbT5tPFwvZW0+IHJlcHJlc2VudHMgdGhlIG51bWJlciBvZiB0dXJucyBpbiB3aGljaCBsaW5lIHNlZ21lbnRzIGhhdmUgYmVlbiBkcmF3bi4gRXZlcnkgcG9pbnQgaGFzIGEgdW5pcXVlIG51bWJlciBmcm9tIDAgdG8gPGVtPm48XC9lbT4gJm1pbnVzOyAxLCBhbmQgbm8gdGhyZWUgcG9pbnRzIGxpZSBvbiBhIHNhbWUgbGluZS4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIDxlbT5tPFwvZW0+IGxpbmVzIGNvbnRhaW5zIHR3byBudW1iZXJzIG9mIHBvaW50cyB3aGljaCBhcmUgdGhlIGVuZCBwb2ludHMgb2YgdGhlIGxpbmUgc2VnbWVudHMgZWFjaCBwbGF5ZXIgZHJldyBpbiB0aGUgPGVtPmk8XC9lbT4tdGggdHVybiAoMSAmbGU7IDxlbT5pPFwvZW0+ICZsZTsgPGVtPm08XC9lbT4pLjxzcGFuIHN0eWxlPVwiZGlzcGxheTogbm9uZTtcIj4mbmJzcDs8XC9zcGFuPjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUuIFRoZSBsaW5lIHNob3VsZCBjb250YWluIHRoZSBudW1iZXIgb2YgdGhlIHR1cm4gaW4gd2hpY2ggdGhlIGN5Y2xlIGhhcyBiZWVuIGZpcnN0IGNyZWF0ZWQsIGkuZS4sIHRoZSBnYW1lIGhhcyBiZWVuIG92ZXIsIGFuZCAwIGlmIHRoZSBnYW1lIHdhcyBub3Qgb3ZlciBmb3IgPGVtPm08XC9lbT4gdHVybnMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

접근 방법

- 분리집합을 통해 부분집합들을 갱신해나가다가 유니온 파인드를 했을 때 같은 숫자가 나온 경우 몇번째 차례였는지 출력한다.

코드

# https://www.acmicpc.net/problem/20040
# 접근 방법
# 분리집합을 통해 부분집합들을 갱신해나가다가 유니온 파인드를 했을 때 같은 숫자가 나온 경우 몇번째 차례였는지 출력한다.
def get_parent(idx):
    if parent[idx] == idx:
        return idx
    index = get_parent(parent[idx])
    parent[idx] = index
    return index

def find_union(point1, point2):
    p1 = get_parent(point1)
    p2 = get_parent(point2)
    if p1 == p2:
        return True
    
    if p1 < p2:
        parent[p2] = p1
    else:
        parent[p1] = p2
    return False

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
parent = [i for i in range(n+1)]
array = [list(map(int, input().split())) for _ in range(m)]
for i in range(1, m+1):
    point1, point2 = array[i-1]
    check = find_union(point1, point2)
    if check:
        break
    
if check:
    print(i)
else:
    print(0)