시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 452 65 55 21.154%

문제

1번부터 N번까지 번호가 매겨져 있는 N개의 마을과 마을을 연결하는 M개의 일방통행 도로로 이루어진 나라가 있다. 이 나라에서는 자전거 경주 대회를 개최하려고 한다. 경주는 1번 마을에서 시작해야 하고, 2번 마을에서 끝나야 한다.

자전거 경주를 개최할 수 있는 경로의 수는 총 몇 가지가 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 100,000)

다음 M개 줄에는 도로의 정보를 나타내는 A와 B가 주어진다. 이 정보는 A에서 B로 향하는 도로를 나타낸다.

두 마을이 하나 이상의 도로로 연결되어 있을 수도 있다.

출력

첫째 줄에 가능한 자전거 경주 대회 경로의 수를 출력한다. 수가 9자리를 넘어가는 경우에는 뒤의 9자리만 출력하면 된다. 만약, 경로의 수가 무한대인 경우에는 "inf"를 출력한다.

예제 입력 1

6 7
1 3
1 4
3 2
4 2
5 6
6 5
3 4

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjMwNDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3OTBcdWM4MDRcdWFjNzAgXHVhY2JkXHVjOGZjIFx1YzkwMFx1YmU0NFx1ZDU1OFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+MVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMjk0IE5cdWFjMWNcdWM3NTggXHViOWM4XHVjNzQ0XHVhY2ZjIFx1YjljOFx1Yzc0NFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgTVx1YWMxY1x1Yzc1OCBcdWM3N2NcdWJjMjlcdWQxYjVcdWQ1ODkmbmJzcDtcdWIzYzRcdWI4NWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YjA5OFx1Yjc3Y1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWIwOThcdWI3N2NcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjNzkwXHVjODA0XHVhYzcwIFx1YWNiZFx1YzhmYyBcdWIzMDBcdWQ2OGNcdWI5N2MgXHVhYzFjXHVjZDVjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhY2JkXHVjOGZjXHViMjk0IDFcdWJjODggXHViOWM4XHVjNzQ0XHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFjZTAsIDJcdWJjODggXHViOWM4XHVjNzQ0XHVjNWQwXHVjMTFjIFx1YjA1ZFx1YjA5OFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc5MFx1YzgwNFx1YWM3MCBcdWFjYmRcdWM4ZmNcdWI5N2MgXHVhYzFjXHVjZDVjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHViODVjXHVjNzU4IFx1YzIxOFx1YjI5NCBcdWNkMWQgXHViYTg3IFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwLDAwMCwgMSAmbGU7IE0gJmxlOyAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViM2M0XHViODVjXHVjNzU4IFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgQVx1YzY0MCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzgxNVx1YmNmNFx1YjI5NCBBXHVjNWQwXHVjMTFjIEJcdWI4NWMgXHVkNWE1XHVkNTU4XHViMjk0IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWI5YzhcdWM3NDRcdWM3NzQgXHVkNTU4XHViMDk4IFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWIzYzRcdWI4NWNcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1Yzc5MFx1YzgwNFx1YWM3MCBcdWFjYmRcdWM4ZmMgXHViMzAwXHVkNjhjIFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWMyMThcdWFjMDAgOVx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWIxMThcdWM1YjRcdWFjMDBcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YjRhNFx1Yzc1OCA5XHVjNzkwXHViOWFjXHViOWNjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVhY2JkXHViODVjXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWJiMzRcdWQ1NWNcdWIzMDBcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0ICZxdW90O2luZiZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzA0NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJJQ0lLTEkiLCJkZXNjcmlwdGlvbiI6IjxwPkEgYmljeWNsZSByYWNlIGlzIGJlaW5nIG9yZ2FuaXplZCBpbiBhIGxhbmQgZmFyLCBmYXIgYXdheS4gVGhlcmUgYXJlIE4gdG93biBpbiB0aGUgbGFuZCwgbnVtYmVyZWQgMSB0aHJvdWdoIE4uIFRoZXJlIGFyZSBhbHNvIE0gb25lLXdheSByb2FkcyBiZXR3ZWVuIHRoZSB0b3ducy4gVGhlIHJhY2Ugd2lsbCBzdGFydCBpbiB0b3duIDEgYW5kIGVuZCBpbiB0b3duIDIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhvdyBtYW55IGRpZmZlcmVudCB3YXlzIGNhbiB0aGUgcm91dGUgYmUgc2V0PyBUd28gcm91dGVzIGFyZSBjb25zaWRlcmVkIGRpZmZlcmVudCBpZiB0aGV5IGRvIG5vdCB1c2UgdGhlIGV4YWN0IHNhbWUgcm9hZHMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgTSAoMSAmbGU7IE4gJmxlOyAxMCAwMDAsIDEgJmxlOyBNICZsZTsgMTAwIDAwMCksIHRoZSBudW1iZXIgb2YgdG93bnMgYW5kIHJvYWRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IE0gbGluZXMgY29udGFpbnMgdHdvIGRpZmZlcmVudCBpbnRlZ2VycyBBIGFuZCBCLCByZXByZXNlbnRpbmcgYSByb2FkIGJldHdlZW4gdG93bnMgQSBhbmQgQi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VG93bnMgbWF5IGJlIGNvbm5lY3RlZCBieSBtb3JlIHRoYW4gb25lIHJvYWQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBudW1iZXIgb2YgZGlzdGluY3Qgcm91dGVzIHRoYXQgY2FuIGJlIHNldCBvbiBhIHNpbmdsZSBsaW5lLiBJZiB0aGF0IG51bWJlciBoYXMgbW9yZSB0aGFuIG5pbmUgZGlnaXRzLCBvdXRwdXQgb25seSB0aGUgbGFzdCBuaW5lIGRpZ2l0cyBvZiB0aGUgbnVtYmVyLiBJZiB0aGVyZSBhcmUgaW5maW5pdGVseSBtYW55IHJvdXRlcywgb3V0cHV0ICZxdW90O2luZiZxdW90Oy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #3 5번

  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: Green55
  • 문제의 오타를 찾은 사람: hyunynim