시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 83 12 6 12.500%

문제

암호기법 덕분에 우리는 의도된 수신자 이외에 누구도 메세지를 읽을 수 없도록 암호화 할 수 있다. 하지만, 암호화된 메세지들은 실제로 수신자에게 도달하지 않을 경우 쓸모가 없다. 오늘날, 컴퓨터 네트워크는 이러한 메세지들을 전송하는 가장 일반적인 방법이다. 이 문제에서는 네트워크 공급자들이 해결해야 하는 문제에 대해 공부한다. 메세지는 암호화되어있기 때문에, 네트워크 보안에 대해 더이상 신경쓰지 않아도 됨을 기억해라.

컴퓨터(서버)를 연결하는 네트워크 케이블들은 다른 회사에 속해 있다. 새로 만들어진 독점 금지법은 모든 회사가 각 서버에서 케이블을 2개보다 많이 소유하지 못하게 한다. 또한, 자원 낭비를 피하기 위해 각 회사가 불필요한 케이블을 소유하면 안 된다는 내용도 있다. (즉, 어떠한 케이블을 제거하면 이전에 연결되어있던 두 개의 서버는 연결이 끊어진다.)  회사들은 케이블을 계속 사고 팔기 때문에, 이러한 규정을 시행하는 것은 매우 어렵다. 당신의 임무는 이러한 규정의 시행을 도와주는 프로그램을 작성하는 것이다!

입력

입력은 몇가지 예시를 포함한다. 각 예시의 첫 번째 줄에는 공백으로 구분된 네 개의 정수 N, M, C, T가 주어진다. N은 서버의 개수(1<=N<=8000), M은 케이블의 개수(0<=M<=100 000), C는 회사의 개수(1<=C<=100), T는 케이블 판매 거래수(0<=T<=100 000)를 나타낸다.

다음의 M행은 케이블에 대한 내용이다. 각 줄에는 공백으로 구분된 세개의 정수 Sj1, Sj2, Kj가 주어진다. Sj1과 Sj2는 해당 케이블로 연결된 서버의 번호이고(1<=Sj1<Sj2<=n), Kj는 처음 케이블을 소유하고 있는 회사의 번호이다. 각 서버 쌍에는 최대 하나의 케이블만 연결된다. 초기 상태는 규정을 만족한다. 즉, 각 회사는 각 서버에 최대 2개의 케이블을 소유하고 있으며, 한 회사가 소유한 케이블 시스템에는 사이클이 없다.

마지막으로 다음의 T행에는 정수 Si1, Si2, Ki가 주어진다. 하나의 거래에 대해 Ki (1<=Ki<=C) 회사가 서버 Si1와 Si2 사이의 케이블을 구매하려는 것을 나타낸다.

마지막 예시의 다음에는 4개의 0이 주어진다.

출력

각각의 예시에 대해, 거래의 결과를 나타내는 T개의 행을 출력하라. 가능한 출력결과는 다음과 같다.

  • "No such cable." : 서버 쌍이 케이블로 연결되지 않을 때
  • "Already owned." : 이미 회사 Ki가 케이블을 가지고 있을 때
  • "Forbidden: monopoly." : 회사 Ki가 이미 서버 Si1이나 Si2에서 2개의 케이블을 가지고 있을 때
  • "Forbidden: redundant." : 회사 Ki가 서버 Si1과 Si2에 대해 각각 최대 1개의 케이블을 가지고 있으나 소유권을 부여할 경우 Ki가 가진 케이블이 사이클을 형성할 때
  • "Sold." : 위의 제한 사항 중 하나도 적용되지 않을 때. 이 경우 서버 Si1과 Si2에 대한 케이블의 소유권은 이후 거래를 위해 Ki에게 옮겨간다.
각 인스턴스 뒤에는 한 개의 빈 줄을 출력해라.

예제 입력 1

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

예제 출력 1

Sold.
Already owned.
Forbidden: monopoly.
Forbidden: redundant.
No such cable.

Already owned.
W3sicHJvYmxlbV9pZCI6IjM0MjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWMwYzFcdWQ1NWMgXHVhZGRjXHVjODE1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NTRcdWQ2MzhcdWFlMzBcdWJjOTUgXHViMzU1XHViZDg0XHVjNWQwIFx1YzZiMFx1YjlhY1x1YjI5NCBcdWM3NThcdWIzYzRcdWI0MWMgXHVjMjE4XHVjMmUwXHVjNzkwIFx1Yzc3NFx1YzY3OFx1YzVkMCBcdWIyMDRcdWFkNmNcdWIzYzQgXHViYTU0XHVjMTM4XHVjOWMwXHViOTdjIFx1Yzc3ZFx1Yzc0NCBcdWMyMTggXHVjNWM2XHViM2M0XHViODVkIFx1YzU1NFx1ZDYzOFx1ZDY1NCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWM1NTRcdWQ2MzhcdWQ2NTRcdWI0MWMgXHViYTU0XHVjMTM4XHVjOWMwXHViNGU0XHVjNzQwIFx1YzJlNFx1YzgxY1x1Yjg1YyBcdWMyMThcdWMyZTBcdWM3OTBcdWM1ZDBcdWFjOGMgXHViM2M0XHViMmVjXHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWFjYmRcdWM2YjAgXHVjNGY4XHViYWE4XHVhYzAwIFx1YzVjNlx1YjJlNC4gXHVjNjI0XHViMjk4XHViMGEwLCBcdWNlZjRcdWQ0ZThcdWQxMzAgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHViMjk0IFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWJhNTRcdWMxMzhcdWM5YzBcdWI0ZTRcdWM3NDQgXHVjODA0XHVjMWExXHVkNTU4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM3N2NcdWJjMThcdWM4MDFcdWM3NzggXHViYzI5XHViYzk1XHVjNzc0XHViMmU0LiBcdWM3NzQgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjXHViMjk0IFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2YyBcdWFjZjVcdWFlMDlcdWM3OTBcdWI0ZTRcdWM3NzQgXHVkNTc0XHVhY2IwXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWJiMzhcdWM4MWNcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YWNmNVx1YmQ4MFx1ZDU1Y1x1YjJlNC4gXHViYTU0XHVjMTM4XHVjOWMwXHViMjk0IFx1YzU1NFx1ZDYzOFx1ZDY1NFx1YjQxOFx1YzViNFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2YyBcdWJjZjRcdWM1NDhcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YjM1NFx1Yzc3NFx1YzBjMSBcdWMyZTBcdWFjYmRcdWM0ZjBcdWM5YzAgXHVjNTRhXHVjNTQ0XHViM2M0IFx1YjQyOFx1Yzc0NCBcdWFlMzBcdWM1YjVcdWQ1NzRcdWI3N2MuPFwvcD5cclxuXHJcbjxwPlx1Y2VmNFx1ZDRlOFx1ZDEzMChcdWMxMWNcdWJjODQpXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmMgXHVjZjAwXHVjNzc0XHViZTE0XHViNGU0XHVjNzQwIFx1YjJlNFx1Yjk3OCBcdWQ2OGNcdWMwYWNcdWM1ZDAgXHVjMThkXHVkNTc0IFx1Yzc4OFx1YjJlNC4gXHVjMGM4XHViODVjIFx1YjljY1x1YjRlNFx1YzViNFx1YzljNCBcdWIzYzVcdWM4MTAgXHVhZTA4XHVjOWMwXHViYzk1XHVjNzQwIFx1YmFhOFx1YjRlMCBcdWQ2OGNcdWMwYWNcdWFjMDAgXHVhYzAxIFx1YzExY1x1YmM4NFx1YzVkMFx1YzExYyBcdWNmMDBcdWM3NzRcdWJlMTRcdWM3NDQgMlx1YWMxY1x1YmNmNFx1YjJlNCBcdWI5Y2VcdWM3NzQgXHVjMThjXHVjNzIwXHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1OFx1YWM4YyBcdWQ1NWNcdWIyZTQuIFx1YjYxMFx1ZDU1YywgXHVjNzkwXHVjNmQwIFx1YjBhZFx1YmU0NFx1Yjk3YyBcdWQ1M2NcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YWMwMSBcdWQ2OGNcdWMwYWNcdWFjMDAgXHViZDg4XHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2YwMFx1Yzc3NFx1YmUxNFx1Yzc0NCBcdWMxOGNcdWM3MjBcdWQ1NThcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNFx1YjI5NCBcdWIwYjRcdWM2YTlcdWIzYzQgXHVjNzg4XHViMmU0LiAoXHVjOTg5LCBcdWM1YjRcdWI1YTBcdWQ1NWMgXHVjZjAwXHVjNzc0XHViZTE0XHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU1OFx1YmE3NCBcdWM3NzRcdWM4MDRcdWM1ZDAgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0XHVjNzg4XHViMzU4IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjMTFjXHViYzg0XHViMjk0IFx1YzVmMFx1YWNiMFx1Yzc3NCBcdWIwNGFcdWM1YjRcdWM5YzRcdWIyZTQuKSAmbmJzcDtcdWQ2OGNcdWMwYWNcdWI0ZTRcdWM3NDAgXHVjZjAwXHVjNzc0XHViZTE0XHVjNzQ0IFx1YWNjNFx1YzE4ZCBcdWMwYWNcdWFjZTAgXHVkMzE0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNzc0XHViN2VjXHVkNTVjIFx1YWRkY1x1YzgxNVx1Yzc0NCBcdWMyZGNcdWQ1ODlcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YjllNFx1YzZiMCBcdWM1YjRcdWI4MzVcdWIyZTQuIFx1YjJmOVx1YzJlMFx1Yzc1OCBcdWM3ODRcdWJiMzRcdWIyOTQgXHVjNzc0XHViN2VjXHVkNTVjIFx1YWRkY1x1YzgxNVx1Yzc1OCBcdWMyZGNcdWQ1ODlcdWM3NDQgXHViM2M0XHVjNjQwXHVjOGZjXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0ITxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YmE4N1x1YWMwMFx1YzljMCBcdWM2MDhcdWMyZGNcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTVjXHViMmU0LiBcdWFjMDEgXHVjNjA4XHVjMmRjXHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MWMgXHViMTI0IFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggTiwgTSwgQywgVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgXHVjMTFjXHViYzg0XHVjNzU4IFx1YWMxY1x1YzIxOCgxJmx0Oz1OJmx0Oz04MDAwKSwgTVx1Yzc0MCBcdWNmMDBcdWM3NzRcdWJlMTRcdWM3NTggXHVhYzFjXHVjMjE4KDAmbHQ7PU0mbHQ7PTEwMCAwMDApLCBDXHViMjk0IFx1ZDY4Y1x1YzBhY1x1Yzc1OCBcdWFjMWNcdWMyMTgoMSZsdDs9QyZsdDs9MTAwKSwgVFx1YjI5NCBcdWNmMDBcdWM3NzRcdWJlMTQgXHVkMzEwXHViOWU0IFx1YWM3MFx1Yjc5OFx1YzIxOCgwJmx0Oz1UJmx0Oz0xMDAgMDAwKVx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0Y1x1Yzc1OCBNXHVkNTg5XHVjNzQwIFx1Y2YwMFx1Yzc3NFx1YmUxNFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHViMGI0XHVjNmE5XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MWMgXHVjMTM4XHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBTPHN1Yj5qMTxcL3N1Yj4sIFM8c3ViPmoyPFwvc3ViPiwgSzxzdWI+ajxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBTPHN1Yj5qMTxcL3N1Yj5cdWFjZmMgUzxzdWI+ajI8XC9zdWI+XHViMjk0IFx1ZDU3NFx1YjJmOSBcdWNmMDBcdWM3NzRcdWJlMTRcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDFjIFx1YzExY1x1YmM4NFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM3NzRcdWFjZTAoMSZsdDs9UzxzdWI+ajE8XC9zdWI+Jmx0O1M8c3ViPmoyPFwvc3ViPiZsdDs9biksIEs8c3ViPmo8XC9zdWI+XHViMjk0IFx1Y2M5OFx1Yzc0YyBcdWNmMDBcdWM3NzRcdWJlMTRcdWM3NDQgXHVjMThjXHVjNzIwXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWQ2OGNcdWMwYWNcdWM3NTggXHViYzg4XHVkNjM4XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVjMTFjXHViYzg0IFx1YzMwZFx1YzVkMFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVkNTU4XHViMDk4XHVjNzU4IFx1Y2YwMFx1Yzc3NFx1YmUxNFx1YjljYyBcdWM1ZjBcdWFjYjBcdWI0MWNcdWIyZTQuIFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWIyOTQgXHVhZGRjXHVjODE1XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWFjMDEgXHVkNjhjXHVjMGFjXHViMjk0IFx1YWMwMSBcdWMxMWNcdWJjODRcdWM1ZDAgXHVjZDVjXHViMzAwIDJcdWFjMWNcdWM3NTggXHVjZjAwXHVjNzc0XHViZTE0XHVjNzQ0IFx1YzE4Y1x1YzcyMFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1ZDU1YyBcdWQ2OGNcdWMwYWNcdWFjMDAgXHVjMThjXHVjNzIwXHVkNTVjIFx1Y2YwMFx1Yzc3NFx1YmUxNCBcdWMyZGNcdWMyYTRcdWQxNWNcdWM1ZDBcdWIyOTQgXHVjMGFjXHVjNzc0XHVkMDc0XHVjNzc0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjIFx1YjJlNFx1Yzc0Y1x1Yzc1OCBUXHVkNTg5XHVjNWQwXHViMjk0IFx1YzgxNVx1YzIxOCBTPHN1Yj5pMTxcL3N1Yj4sIFM8c3ViPmkyPFwvc3ViPiwgSzxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQ1NThcdWIwOThcdWM3NTggXHVhYzcwXHViNzk4XHVjNWQwIFx1YjMwMFx1ZDU3NCBLPHN1Yj5pPFwvc3ViPiAoMSZsdDs9SzxzdWI+aTxcL3N1Yj4mbHQ7PUMpIFx1ZDY4Y1x1YzBhY1x1YWMwMCBcdWMxMWNcdWJjODQgUzxzdWI+aTE8XC9zdWI+XHVjNjQwIFM8c3ViPmkyPFwvc3ViPiBcdWMwYWNcdWM3NzRcdWM3NTggXHVjZjAwXHVjNzc0XHViZTE0XHVjNzQ0IFx1YWQ2Y1x1YjllNFx1ZDU1OFx1YjgyNFx1YjI5NCBcdWFjODNcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5YzhcdWM5YzBcdWI5YzkgXHVjNjA4XHVjMmRjXHVjNzU4IFx1YjJlNFx1Yzc0Y1x1YzVkMFx1YjI5NCA0XHVhYzFjXHVjNzU4IDBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM2MDhcdWMyZGNcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWFjNzBcdWI3OThcdWM3NTggXHVhY2IwXHVhY2ZjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBUXHVhYzFjXHVjNzU4IFx1ZDU4OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWNkOWNcdWI4MjVcdWFjYjBcdWFjZmNcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4mcXVvdDtObyBzdWNoIGNhYmxlLiZxdW90OyA6IFx1YzExY1x1YmM4NCBcdWMzMGRcdWM3NzQgXHVjZjAwXHVjNzc0XHViZTE0XHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzljMCBcdWM1NGFcdWM3NDQgXHViNTRjPFwvbGk+XHJcblx0PGxpPiZxdW90O0FscmVhZHkgb3duZWQuJnF1b3Q7IDogXHVjNzc0XHViYmY4IFx1ZDY4Y1x1YzBhYyBLPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWNmMDBcdWM3NzRcdWJlMTRcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1Yzc0NCBcdWI1NGM8XC9saT5cclxuXHQ8bGk+JnF1b3Q7Rm9yYmlkZGVuOiBtb25vcG9seS4mcXVvdDsgOiBcdWQ2OGNcdWMwYWMgSzxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjNzc0XHViYmY4IFx1YzExY1x1YmM4NCBTPHN1Yj5pMTxcL3N1Yj5cdWM3NzRcdWIwOTggUzxzdWI+aTI8XC9zdWI+XHVjNWQwXHVjMTFjIDJcdWFjMWNcdWM3NTggXHVjZjAwXHVjNzc0XHViZTE0XHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWM3NDQgXHViNTRjPFwvbGk+XHJcblx0PGxpPiZxdW90O0ZvcmJpZGRlbjogcmVkdW5kYW50LiZxdW90OyA6IFx1ZDY4Y1x1YzBhYyBLPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWMxMWNcdWJjODQgUzxzdWI+aTE8XC9zdWI+XHVhY2ZjIFM8c3ViPmkyPFwvc3ViPlx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVhYzAxXHVhYzAxIFx1Y2Q1Y1x1YjMwMCAxXHVhYzFjXHVjNzU4IFx1Y2YwMFx1Yzc3NFx1YmUxNFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjNzNjXHViMDk4IFx1YzE4Y1x1YzcyMFx1YWQ4Y1x1Yzc0NCBcdWJkODBcdWM1ZWNcdWQ1NjAgXHVhY2JkXHVjNmIwIEs8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YWMwMFx1YzljNCBcdWNmMDBcdWM3NzRcdWJlMTRcdWM3NzQgXHVjMGFjXHVjNzc0XHVkMDc0XHVjNzQ0IFx1ZDYxNVx1YzEzMVx1ZDU2MCBcdWI1NGM8XC9saT5cclxuXHQ8bGk+JnF1b3Q7U29sZC4mcXVvdDsgOiBcdWM3MDRcdWM3NTggXHVjODFjXHVkNTVjIFx1YzBhY1x1ZDU2ZCBcdWM5MTEgXHVkNTU4XHViMDk4XHViM2M0IFx1YzgwMVx1YzZhOVx1YjQxOFx1YzljMCBcdWM1NGFcdWM3NDQgXHViNTRjLiBcdWM3NzQgXHVhY2JkXHVjNmIwIFx1YzExY1x1YmM4NCBTPHN1Yj5pMTxcL3N1Yj5cdWFjZmMgUzxzdWI+aTI8XC9zdWI+XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWNmMDBcdWM3NzRcdWJlMTRcdWM3NTggXHVjMThjXHVjNzIwXHVhZDhjXHVjNzQwIFx1Yzc3NFx1ZDZjNCBcdWFjNzBcdWI3OThcdWI5N2MgXHVjNzA0XHVkNTc0IEs8c3ViPmk8XC9zdWI+XHVjNWQwXHVhYzhjIFx1YzYyZVx1YWNhOFx1YWMwNFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48ZGl2Plx1YWMwMSBcdWM3NzhcdWMyYTRcdWQxMzRcdWMyYTQgXHViNGE0XHVjNWQwXHViMjk0IFx1ZDU1YyBcdWFjMWNcdWM3NTggXHViZTQ4IFx1YzkwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NzRcdWI3N2MuPFwvZGl2PlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNDIxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3RyYW5nZSBSZWd1bGF0aW9ucyIsImRlc2NyaXB0aW9uIjoiPHA+VGhhbmsgdG8gY3J5cHRvZ3JhcGh5LCB3ZSBhcmUgYWJsZSB0byBlbmNyeXB0IG1lc3NhZ2VzIHN1Y2ggdGhhdCBub29uZSAoZXhjZXB0IHRoZSBpbnRlbmRlZCByZWNpcGllbnQpIGlzIGFibGUgdG8gcmVhZCB0aGVtLiBIb3dldmVyLCBlbmNyeXB0ZWQgbWVzc2FnZXMgYXJlIG9mIG5vIHVzZSBpZiB0aGV5IGRvIG5vdCBhY3R1YWxseSByZWFjaCB0aGUgcmVjaXBpZW50LiBUaGVzZSBkYXlzLCBjb21wdXRlciBuZXR3b3JrIGlzIHRoZSBtb3N0IHR5cGljYWwgbWVhbiB0byBzZW5kIHN1Y2ggbWVzc2FnZXMuIEluIHRoaXMgcHJvYmxlbSwgd2Ugd2lsbCBzdHVkeSB0aGUgaXNzdWVzIHRoZSBuZXR3b3JraW5nIHByb3ZpZGVycyBoYXZlIHRvIHNvbHZlLiBBbmQgcmVtZW1iZXI6IHNpbmNlIHRoZSBtZXNzYWdlIGlzIGVuY3J5cHRlZCwgd2UgZG8gbm90IG5lZWQgdG8gY2FyZSBhYm91dCB0aGUgbmV0d29yayBwcml2YWN5IGFueW1vcmUuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXR3b3JrIGNhYmxlcyBqb2luaW5nIGNvbXB1dGVycyAoc2VydmVycykgYmVsb25nIHRvIGRpZmZlcmVudCBjb21wYW5pZXMuIEEgbmV3IGFudGltb25vcG9seSBsZWdpc2xhdGlvbiBwcmV2ZW50cyBhbnkgY29tcGFueSBmcm9tIG93bmluZyBtb3JlIHRoYW4gdHdvIGNhYmxlcyBmcm9tIGVhY2ggc2VydmVyLiBGdXJ0aGVybW9yZSwgdG8gYXZvaWQgd2FzdGluZyByZXNvdXJjZXMsIHRoZXJlIGlzIGFsc28gYSBsYXcgc3BlY2lmeWluZyB0aGF0IHRoZSBjYWJsZSBzeXN0ZW0gb3duZWQgYnkgYW55IHNpbmdsZSBjb21wYW55IGNhbm5vdCBiZSByZWR1bmRhbnQsIGkuZS4sIHJlbW92YWwgb2YgYW55IG9mIHRoZSBjYWJsZXMgd2lsbCBkaXNjb25uZWN0IHNvbWUgdHdvIHByZXZpb3VzbHkgY29ubmVjdGVkIHNlcnZlcnMuIFNpbmNlIHRoZSBjb21wYW5pZXMgYnV5IGFuZCBzZWxsIHRoZSBjYWJsZXMgYWxsIHRoZSB0aW1lLCBpdCBpcyBxdWl0ZSBkaWZmaWN1bHQgdG8gZW5mb3JjZSB0aGVzZSByZWd1bGF0aW9ucy4gWW91ciB0YXNrIGlzIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGRvZXMgc28uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgc2V2ZXJhbCBpbnN0YW5jZXMuIFRoZSBmaXJzdCBsaW5lIG9mIGVhY2ggaW5zdGFuY2UgY29udGFpbnMgZm91ciBpbnRlZ2VycyBOLCBNLCBDIGFuZCBUIHNlcGFyYXRlZCBieSBzcGFjZXMgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIHNlcnZlcnMgKDEgJmxlOyBOICZsZTsgOCAwMDApLCB0aGUgbnVtYmVyIG9mIGNhYmxlcyAoMCAmbGU7IE0gJmxlOyAxMDAgMDAwKSwgdGhlIG51bWJlciBvZiBjb21wYW5pZXMgKDEgJmxlOyBDICZsZTsgMTAwKSwgYW5kIHRoZSBudW1iZXIgb2YgY2FibGUtc2VsbGluZyB0cmFuc2FjdGlvbnMgKDAgJmxlOyBUICZsZTsgMTAwIDAwMCksIHJlc3BlY3RpdmVseS48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBNIGxpbmVzIGRlc2NyaWJlIHRoZSBjYWJsZXMuIEVhY2ggb2YgdGhlbSBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBTPHN1Yj5qMTxcL3N1Yj4sIFM8c3ViPmoyPFwvc3ViPiBhbmQgSzxzdWI+ajxcL3N1Yj4gLCBzZXBhcmF0ZWQgYnkgc3BhY2VzLCBnaXZpbmcgdGhlIG51bWJlcnMgb2YgdGhlIHNlcnZlcnMgUzxzdWI+ajE8XC9zdWI+IGFuZCBTPHN1Yj5qMjxcL3N1Yj4gKDEgJmxlOyBTPHN1Yj5qMTxcL3N1Yj4gJmx0OyBTPHN1Yj5qMjxcL3N1Yj4gJmxlOyBuKSBqb2luZWQgYnkgdGhhdCBjYWJsZSBhbmQgdGhlIG51bWJlciBvZiB0aGUgY29tcGFueSBLPHN1Yj5qPFwvc3ViPiAoMSAmbGU7IEs8c3ViPmo8XC9zdWI+ICZsZTsgQykgaW5pdGlhbGx5IG93bmluZyB0aGUgY2FibGUuIEZvciBlYWNoIHBhaXIgb2Ygc2VydmVycywgdGhlcmUgaXMgYXQgbW9zdCBvbmUgY2FibGUgam9pbmluZyB0aGVtLiBUaGUgaW5pdGlhbCBzdGF0ZSBzYXRpc2ZpZXMgdGhlIHJlZ3VsYXRpb25zLCBpLmUuLCBlYWNoIGNvbXBhbnkgb3ducyBhdCBtb3N0IHR3byBjYWJsZXMgaW5jaWRlbnQgd2l0aCBlYWNoIHNlcnZlciwgYW5kIHRoZSBzeXN0ZW0gb2YgY2FibGVzIG93bmVkIGJ5IGEgc2luZ2xlIGNvbXBhbnkgaGFzIG5vIGN5Y2xlcy48XC9wPlxyXG5cclxuPHA+RmluYWxseSwgZWFjaCBvZiB0aGUgbmV4dCBUIGxpbmVzIGNvbnRhaW5zIGludGVnZXJzIFM8c3ViPmkxPFwvc3ViPiwgUzxzdWI+aTI8XC9zdWI+IGFuZCBLPHN1Yj5pPFwvc3ViPiBkZXNjcmliaW5nIG9uZSB0cmFuc2FjdGlvbiBpbiB3aGljaCB0aGUgY29tcGFueSBLPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IEtpICZsZTsgQykgdHJpZXMgdG8gYnV5IGEgY2FibGUgYmV0d2VlbiBzZXJ2ZXJzIFM8c3ViPmkxPFwvc3ViPiBhbmQgUzxzdWI+aTI8XC9zdWI+ICgxICZsZTsgUzxzdWI+aTE8XC9zdWI+ICZsdDsgUzxzdWI+aTI8XC9zdWI+ICZsZTsgTikuPFwvcD5cclxuXHJcbjxwPlRoZSBsYXN0IGluc3RhbmNlIGlzIGZvbGxvd2VkIGJ5IGEgbGluZSBjb250YWluaW5nIGZvdXIgemVyb3MuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggaW5wdXQgaW5zdGFuY2UsIG91dHB1dCBUIGxpbmVzIGRlc2NyaWJpbmcgdGhlIG91dGNvbWUgb2YgdGhlIHRyYW5zYWN0aW9ucy4gVGhlIHBvc3NpYmxlIG91dGNvbWVzIGFyZTxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiZsZHF1bztObyBzdWNoIGNhYmxlLiZyZHF1bzsgaWYgdGhlIHBhaXIgb2Ygc2VydmVycyBpcyBub3Qgam9pbmVkIGJ5IGEgY2FibGUsPFwvbGk+XHJcblx0PGxpPiZsZHF1bztBbHJlYWR5IG93bmVkLiZyZHF1bzsgaWYgdGhlIGNhYmxlIGlzIGFscmVhZHkgb3duZWQgYnkgdGhlIGNvbXBhbnkgSzxzdWI+aTxcL3N1Yj4sPFwvbGk+XHJcblx0PGxpPiZsZHF1bztGb3JiaWRkZW46IG1vbm9wb2x5LiZyZHF1bzsgaWYgdGhlIGNvbXBhbnkgSzxzdWI+aTxcL3N1Yj4gYWxyZWFkeSBvd25zIHR3byBjYWJsZXMgYXQgUzxzdWI+aTE8XC9zdWI+IG9yIFM8c3ViPmkyPFwvc3ViPiw8XC9saT5cclxuXHQ8bGk+JmxkcXVvO0ZvcmJpZGRlbjogcmVkdW5kYW50LiZyZHF1bzsgaWYgSzxzdWI+aTxcL3N1Yj4gb3ducyBhdCBtb3N0IG9uZSBjYWJsZSBhdCBlYWNoIG9mIFM8c3ViPmkxPFwvc3ViPiBhbmQgUzxzdWI+aTI8XC9zdWI+LCBidXQgZ3JhbnRpbmcgdGhlIG93bmVyc2hpcCB3b3VsZCBjcmVhdGUgYSBjeWNsZSBvZiBjYWJsZXMgb3duZWQgYnkgSzxzdWI+aTxcL3N1Yj4sPFwvbGk+XHJcblx0PGxpPiZsZHF1bztTb2xkLiZyZHF1bzsgaWYgbm9uZSBvZiB0aGUgYWJvdmUgcmVzdHJpY3Rpb25zIGFwcGx5LiBJbiB0aGlzIGNhc2UsIHRoZSBvd25lcnNoaXAgb2YgdGhlIGNhYmxlIGJldHdlZW4gUzxzdWI+aTE8XC9zdWI+IGFuZCBTPHN1Yj5pMjxcL3N1Yj4gY2hhbmdlcyB0byBLPHN1Yj5pPFwvc3ViPiBmb3IgdGhlIHB1cnBvc2Ugb2YgZnVydGhlciB0cmFuc2FjdGlvbnMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+UHJpbnQgb25lIGVtcHR5IGxpbmUgYWZ0ZXIgZWFjaCBpbnN0YW5jZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Europe > Central European Regional Contest > CERC 2011 F번