시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 486 99 64 22.069%

문제

민혁이는 매주 금요일마다 지수와 함께 논다. 이번 주 금요일은 지수와 민혁이가 친구가 된지 십 년이 되는 날이다. 따라서, 둘은 엄청난 게임을 하기로 결정했다. 민혁이는 바닥이 흙인 운동장을 예약했고, 지수는 조약돌 한 개를 들고 왔다.

먼저 민혁이는 운동장 바닥에 나뭇가지로 방향 그래프를 그린다. 이 그래프에서 모든 정점은 많아야 한 개의 나가는 간선(outgoing edge)를 가질 수 있다. 그 다음 민혁이는 조약돌을 한 정점 위에 올려 놓는다. 만약, 조약돌이 있는 정점에 나가는 간선이 있다면, 조약돌은 그 간선을 통해서 이동할 수 없을 때까지 계속해서 이동한다. 더 이상 이동할 수 있는 정점이 없다면, 조약돌은 그 자리에서 멈춘다. 조약돌은 그래프를 무한히 이동할 수도 있고, 방문하지 않는 정점이 있을 수도 있다.

민혁이는 지수가 게임의 규칙을 확실하게 이해했는지 알기 위해서 다음과 같은 두 가지 질문을 하려고 한다.

  • 1 X - 조약돌을 정점 X에 놓았을 때, 조약돌이 무한히 움직이지 않는다면 조약돌이 멈추는 정점의 번호는 몇 번인가?
  • 2 X - 정점 X에서 나가는 간선을 지운다. (항상 나가는 간선이 있는 정점만 주어진다)

민혁이의 질문이 주어졌을 때, 지수의 답변을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 그래프의 정점의 개수 N이 주어진다. (1 ≤ N ≤ 300,000)

둘째 줄에는 각 정점의 나가는 간선이 공백으로 구분되어서 주어진다. 정점의 번호는 1부터 시작하며, 나가는 간선이 없는 경우에는 0이 주어진다.

셋째 줄에는 민혁이의 질문의 수 Q가 주어진다. (1 ≤ Q ≤ 300,000)

넷째 줄부터 Q개 줄에는 문제 설명에 나온 질문 형식대로 민혁이의 질문이 주어진다.

출력

1로 시작하는 쿼리가 주어질때 마다, 조약돌이 멈추는 정점의 번호를 한 줄에 하나씩 출력한다. 만약, 어떤 정점에 멈추지 않고 무한히 이동한다면, CIKLUS를 출력한다.

예제 입력 1

3
2 3 1
7
1 1
1 2
2 1
1 2
1 1
2 2
1 2

예제 출력 1

CIKLUS
CIKLUS
1
1
2
W3sicHJvYmxlbV9pZCI6IjI4NDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YzhcdWJlMTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmJmY1x1ZDYwMVx1Yzc3NFx1YjI5NCBcdWI5ZTRcdWM4ZmMgXHVhZTA4XHVjNjk0XHVjNzdjXHViOWM4XHViMmU0IFx1YzljMFx1YzIxOFx1YzY0MCBcdWQ1NjhcdWFlZDggXHViMTdjXHViMmU0LiBcdWM3NzRcdWJjODggXHVjOGZjIFx1YWUwOFx1YzY5NFx1Yzc3Y1x1Yzc0MCBcdWM5YzBcdWMyMThcdWM2NDAgXHViYmZjXHVkNjAxXHVjNzc0XHVhYzAwIFx1Y2U1Y1x1YWQ2Y1x1YWMwMCBcdWI0MWNcdWM5YzAgXHVjMmVkIFx1YjE0NFx1Yzc3NCBcdWI0MThcdWIyOTQgXHViMGEwXHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YjQ1OFx1Yzc0MCBcdWM1YzRcdWNjYWRcdWIwOWMgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWFjYjBcdWM4MTVcdWQ1ODhcdWIyZTQuIFx1YmJmY1x1ZDYwMVx1Yzc3NFx1YjI5NCBcdWJjMTRcdWIyZTVcdWM3NzQgXHVkNzU5XHVjNzc4IFx1YzZiNFx1YjNkOVx1YzdhNVx1Yzc0NCBcdWM2MDhcdWM1N2RcdWQ1ODhcdWFjZTAsIFx1YzljMFx1YzIxOFx1YjI5NCBcdWM4NzBcdWM1N2RcdWIzY2MgXHVkNTVjIFx1YWMxY1x1Yjk3YyBcdWI0ZTRcdWFjZTAgXHVjNjU0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhM2NcdWM4MDAgXHViYmZjXHVkNjAxXHVjNzc0XHViMjk0IFx1YzZiNFx1YjNkOVx1YzdhNSBcdWJjMTRcdWIyZTVcdWM1ZDAgXHViMDk4XHViYjQ3XHVhYzAwXHVjOWMwXHViODVjIFx1YmMyOVx1ZDVhNSBcdWFkZjhcdWI3OThcdWQ1MDRcdWI5N2MgXHVhZGY4XHViOWIwXHViMmU0LiBcdWM3NzQgXHVhZGY4XHViNzk4XHVkNTA0XHVjNWQwXHVjMTFjIFx1YmFhOFx1YjRlMCBcdWM4MTVcdWM4MTBcdWM3NDAgXHViOWNlXHVjNTQ0XHVjNTdjIFx1ZDU1YyBcdWFjMWNcdWM3NTggXHViMDk4XHVhYzAwXHViMjk0IFx1YWMwNFx1YzEyMChvdXRnb2luZyBlZGdlKVx1Yjk3YyBcdWFjMDBcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWJiZmNcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjODcwXHVjNTdkXHViM2NjXHVjNzQ0IFx1ZDU1YyBcdWM4MTVcdWM4MTAgXHVjNzA0XHVjNWQwIFx1YzYyY1x1YjgyNCBcdWIxOTNcdWIyOTRcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjODcwXHVjNTdkXHViM2NjXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM1ZDAgXHViMDk4XHVhYzAwXHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1Yzg3MFx1YzU3ZFx1YjNjY1x1Yzc0MCBcdWFkZjggXHVhYzA0XHVjMTIwXHVjNzQ0IFx1ZDFiNVx1ZDU3NFx1YzExYyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1Yzc0NCBcdWI1NGNcdWFlNGNcdWM5YzAgXHVhY2M0XHVjMThkXHVkNTc0XHVjMTFjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC4gXHViMzU0IFx1Yzc3NFx1YzBjMSBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0LCBcdWM4NzBcdWM1N2RcdWIzY2NcdWM3NDAgXHVhZGY4IFx1Yzc5MFx1YjlhY1x1YzVkMFx1YzExYyBcdWJhNDhcdWNkOThcdWIyZTQuIFx1Yzg3MFx1YzU3ZFx1YjNjY1x1Yzc0MCBcdWFkZjhcdWI3OThcdWQ1MDRcdWI5N2MgXHViYjM0XHVkNTVjXHVkNzg4IFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHVhY2UwLCBcdWJjMjlcdWJiMzhcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYmZjXHVkNjAxXHVjNzc0XHViMjk0IFx1YzljMFx1YzIxOFx1YWMwMCBcdWFjOGNcdWM3ODRcdWM3NTggXHVhZGRjXHVjZTU5XHVjNzQ0IFx1ZDY1NVx1YzJlNFx1ZDU1OFx1YWM4YyBcdWM3NzRcdWQ1NzRcdWQ1ODhcdWIyOTRcdWM5YzAgXHVjNTRjXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YjQ1MCBcdWFjMDBcdWM5YzAgXHVjOWM4XHViYjM4XHVjNzQ0IFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSBYIC0gXHVjODcwXHVjNTdkXHViM2NjXHVjNzQ0IFx1YzgxNVx1YzgxMCBYXHVjNWQwIFx1YjE5M1x1YzU1OFx1Yzc0NCBcdWI1NGMsIFx1Yzg3MFx1YzU3ZFx1YjNjY1x1Yzc3NCBcdWJiMzRcdWQ1NWNcdWQ3ODggXHVjNmMwXHVjOWMxXHVjNzc0XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YmE3NCBcdWM4NzBcdWM1N2RcdWIzY2NcdWM3NzQgXHViYTQ4XHVjZDk0XHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgXHViYTg3IFx1YmM4OFx1Yzc3OFx1YWMwMD88XC9saT5cclxuXHQ8bGk+MiBYIC0gXHVjODE1XHVjODEwIFhcdWM1ZDBcdWMxMWMgXHViMDk4XHVhYzAwXHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc0NCBcdWM5YzBcdWM2YjRcdWIyZTQuIChcdWQ1NmRcdWMwYzEgXHViMDk4XHVhYzAwXHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjODE1XHVjODEwXHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCk8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWJiZmNcdWQ2MDFcdWM3NzRcdWM3NTggXHVjOWM4XHViYjM4XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzljMFx1YzIxOFx1Yzc1OCBcdWIyZjVcdWJjYzBcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAzMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWM4MTVcdWM4MTBcdWM3NTggXHViMDk4XHVhYzAwXHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjODE1XHVjODEwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAxXHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YmE3MCwgXHViMDk4XHVhYzAwXHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IDBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmJmY1x1ZDYwMVx1Yzc3NFx1Yzc1OCBcdWM5YzhcdWJiMzhcdWM3NTggXHVjMjE4IFFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFEgJmxlOyAzMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIxMzdcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIFFcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmIzOFx1YzgxYyBcdWMxMjRcdWJhODVcdWM1ZDAgXHViMDk4XHVjNjI4IFx1YzljOFx1YmIzOCBcdWQ2MTVcdWMyZGRcdWIzMDBcdWI4NWMgXHViYmZjXHVkNjAxXHVjNzc0XHVjNzU4IFx1YzljOFx1YmIzOFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+MVx1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVjZmZjXHViOWFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOFx1YjU0YyBcdWI5YzhcdWIyZTQsIFx1Yzg3MFx1YzU3ZFx1YjNjY1x1Yzc3NCBcdWJhNDhcdWNkOTRcdWIyOTQgXHVjODE1XHVjODEwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjNWI0XHViNWE0IFx1YzgxNVx1YzgxMFx1YzVkMCBcdWJhNDhcdWNkOTRcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YmIzNFx1ZDU1Y1x1ZDc4OCBcdWM3NzRcdWIzZDlcdWQ1NWNcdWIyZTRcdWJhNzQsIENJS0xVU1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjg0MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktVR0xJQ0UiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGFuZCBTbGF2a28gbG92ZSBwbGF5aW5nIHdpdGggbWFyYmxlcy4gT24gYW4gZXhjaXRpbmcgRnJpZGF5LCBNaXJrbyBoYXMgY29tZSB1cCB3aXRoIGEgbWFyYmxlIGdhbWUgd2hpY2ggaGUgd2FudHMgdG8gc2hvdyB0byBTbGF2a28uPFwvcD5cclxuXHJcbjxwPkluIHRoZSBnYW1lLCBNaXJrbyBjb25zdHJ1Y3RzIGEgZGlyZWN0aW9uYWwgZ3JhcGggaW4gd2hpY2ggYWxsIHZlcnRpY2VzIGhhdmUgYXQgbW9zdCBhdCBtb3N0IG9uZSBvdXRnb2luZyBlZGdlLiBUaGVuIGhlIHBsYWNlcyBhIG1hcmJsZSBvbiBvbmUgb2YgdGhlIHZlcnRpY2VzLiBXaGVuZXZlciBhIG1hcmJsZSBpcyBvbiBzb21lIHZlcnRleCBYLCB0aGUgbWFyYmxlIG1vdmVzIHRvIHRoZSBhZGphY2VudCB2ZXJ0ZXggY29ubmVjdGVkIGJ5IGEgc2luZ2xlIGVkZ2UsIGlmIHN1Y2ggZXhpc3RzLiBUaGUgbW92ZW1lbnQgb2YgdGhlIG1hcmJsZSBjb250aW51ZXMgdW50aWwgYSB2ZXJ0ZXggd2l0aCBubyBvdXRnb2luZyBlZGdlIGlzIHZpc2l0ZWQsIHdoZXJlIHRoZSBtYXJibGUgc3RvcHMuIEl0IGlzIGFsc28gcG9zc2libGUgdGhhdCB0aGUgbWFyYmxlIHRyYXZlcnNlcyB0aGUgZ3JhcGggaW5kZWZpbml0ZWx5IGluIGNhc2Ugbm8gc3VjaCB2ZXJ0ZXggaXMgZXZlciB2aXNpdGVkLjxcL3A+XHJcblxyXG48cD5UbyBtYWtlIHN1cmUgdGhhdCBTbGF2a28gdW5kZXJzdGFuZCB0aGUgcnVsZXMgb2YgdGhlIGdhbWUsIE1pcmtvIHdpbGwgYXNrIGEgc2VyaWVzIG9mIHF1ZXJpZXMuIFRoZSB0eXBlcyBvZiBxdWVyaWVzIGFyZSBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgWCAmbmRhc2g7IHVubGVzcyB0aGUgbWFyYmxlIHN0dWNrcyBpbiBhIGxvb3AsIG9uIHdoaWNoIHZlcnRleCB3aWxsIHRoZSBtYXJibGUgc3RvcCBpZiBpdCBpcyBwbGFjZWQgb24gdGhlIHZlcnRleCBYPzxcL2xpPlxyXG5cdDxsaT4yIFggJm5kYXNoOyBkZWxldGUgdGhlIG91dGdvaW5nIGVkZ2Ugb2YgdGhlIHZlcnRleCBYIChpdCBpcyBndWFyYW50ZWVkIHRoYXQgc3VjaCBlZGdlIHdpbGwgYWx3YXlzIGV4aXN0KSZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPk5vdGU6IHF1ZXJpZXMgYXJlIGV4ZWN1dGVkIGluIG9yZGVyIGFuZCBhcmUgY3VtbXVsYXRpdmUgKG9uZSBhZmZlY3RzIGFub3RoZXIpLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYSBwb3N0aXZlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAzMDAgMDAwKSwgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBpbiB0aGUgZ3JhcGguPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBleGFjdGx5IE4gcG9zaXRpdmUgaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLCB3aGVyZSB0aGUgbnVtYmVyIGF0IHBvc2l0aW9uIGkgZGVub3RlcyB0aGUgaW5kZXggb2YgdGhlIGRlc3RpbmF0aW9uIG9mIHRoZSBvdXRnb2luZyBlZGdlIGZyb20gdmVydGV4IHdpdGggaW5kZXggaS4gVGhlIHplcm8gdmFsdWUgcmVwcmVzZW50IHRoYXQgdGhlcmUgaXMgbm8gb3V0Z29pbmcgZWRnZSBmcm9tIHRoZSB2ZXJ0ZXggd2l0aCBpbmRleCBpLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIGxpbmUgY29udGFpbnMgYSBzaW5nbGUgcG9zaXRpdmUgaW50ZWdlciBRICgxICZsZTsgUSAmbGU7IDMwMCAwMDApLCB0aGUgbnVtYmVyIG9mIHF1ZXJpZXMuPFwvcD5cclxuXHJcbjxwPlRoZSByZW1haW5pbmcgUSBsaW5lcyBjb250YWluIHF1ZXJpZXMgaW4gdGhlIGZvcm1hdCBkZXNjcmliZWQgYWJvdmUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggcXVlcnkgb2YgdHlwZSAxLCBvdXRwdXQgdGhlIGluZGV4IG9mIHRoZSB2ZXJ0ZXggd2hlcmUgdGhlIG1hcmJsZSBzdG9wcywgb25lIHBlciBsaW5lLCBpbiB0aGUgb3JkZXIgb2YgdGhlIGV4ZWN1dGlvbiBvZiBxdWVyaWVzLiBJZiB0aGUgbWFyYmxlIG5ldmVyIHN0b3BzLCBvdXRwdXQgQ0lLTFVTIGluc3RlYWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #7 5번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: rdd6584