문제
$r$을 루트로 하는 arborescence $G = (V, E)$란 다음 조건을 만족하는 방향 그래프를 뜻한다.
- 다른 모든 정점 $v$에 대해, $r$에서 $v$로 가는 경로가 정확히 하나 존재한다.
DAG(Directed Acyclic Graph)란 사이클이 없는 유향 그래프를 뜻한다. DAG의 각 간선에 가중치가 부여되었을 때, DAG 위에서의 minimum spanning arborescence 란 다음과 같다.
- DAG위에서의 1ドル$을 루트로 한 arborescence이다.
- DAG 상의 모든 정점을 포함한다.
- 사용된 간선들의 가중치 합이 최소이다. 그런 방법이 여럿 존재한다면 모두 minimum spanning arborescence이다.
정점 $N$개, 유향 간선 $M$개로 이루어진 DAG가 주어진다. $M$개의 간선에 각각 1ドル$이상 $K$이하의 가중치를 붙이는 $K^M$가지의 경우에 대해, minimum spanning arborescence를 구성하는 간선의 가중치 합의 기댓값을 998ドル,244円,353円$으로 나눈 나머지를 구하여라. 중복 간선이 있을 수 있음에 유의하라.
출력
기댓값을 998ドル,244円,353円$으로 나눈 나머지를 출력한다.
즉, 기댓값이 서로소인 두 양의 정수 $a,ドル $b$에 대해 기약분수 $\frac{a}{b}$의 형태로 표현될 때, $b \cdot k \equiv a \pmod{998,244円,353円}$을 만족하는 유일한 정수 $k$ (0ドル \le k < 998,244円,353円$)를 출력한다.
제한
- 1ドル \leq N, M, K \leq 10^5 $
- $ N-1 \leq M $
- 모든 1ドル \le i \le N$에 대하여 $ 1 \leq a_i < b_i \leq N$
- 기존 DAG에서 1번 정점에서 다른 모든 정점에 도달할 수 있다.
서브태스크
| 번호 | 배점 | 제한 | | 1 | 5 | $M = N-1$
|
| 2 | 11 | $M \leq 10, K \leq 2$
|
| 3 | 37 | $N, M, K \leq 1000$
|
| 4 | 47 | 추가적인 제약 조건이 없다.
|
W3sicHJvYmxlbV9pZCI6IjMzODA3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiTWluaW11bSBTcGFubmluZyBBcmJvcmVzY2VuY2UiLCJkZXNjcmlwdGlvbiI6IjxwPiRyJFx1Yzc0NCBcdWI4ZThcdWQyYjhcdWI4NWMgXHVkNTU4XHViMjk0IGFyYm9yZXNjZW5jZSAkRyA9IChWLCBFKSRcdWI3ODAgXHViMmU0XHVjNzRjIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViYzI5XHVkNWE1IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yjk3YyBcdWI3M2JcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViMmU0XHViOTc4IFx1YmFhOFx1YjRlMCBcdWM4MTVcdWM4MTAgJHYkXHVjNWQwIFx1YjMwMFx1ZDU3NCwgJHIkXHVjNWQwXHVjMTFjICR2JFx1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhY2JkXHViODVjXHVhYzAwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWQ1NThcdWIwOTggXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkRBRyhEaXJlY3RlZCBBY3ljbGljIEdyYXBoKVx1Yjc4MCBcdWMwYWNcdWM3NzRcdWQwNzRcdWM3NzQgXHVjNWM2XHViMjk0IFx1YzcyMFx1ZDVhNSBcdWFkZjhcdWI3OThcdWQ1MDRcdWI5N2MgXHViNzNiXHVkNTVjXHViMmU0LiBEQUdcdWM3NTggXHVhYzAxIFx1YWMwNFx1YzEyMFx1YzVkMCBcdWFjMDBcdWM5MTFcdWNlNThcdWFjMDAgXHViZDgwXHVjNWVjXHViNDE4XHVjNWM4XHVjNzQ0IFx1YjU0YywgREFHIFx1YzcwNFx1YzVkMFx1YzExY1x1Yzc1OCBtaW5pbXVtIHNwYW5uaW5nIGFyYm9yZXNjZW5jZSBcdWI3ODAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuXHJcbjx1bD5cclxuXHQ8bGk+REFHXHVjNzA0XHVjNWQwXHVjMTFjXHVjNzU4IDxzcGFuIHN0eWxlPVwiY29sb3I6I2MwMzkyYjtcIj48c3Ryb25nPiQxJDxcL3N0cm9uZz48XC9zcGFuPlx1Yzc0NCBcdWI4ZThcdWQyYjhcdWI4NWMgXHVkNTVjIGFyYm9yZXNjZW5jZVx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+REFHIFx1YzBjMVx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjODEwXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMGFjXHVjNmE5XHViNDFjIFx1YWMwNFx1YzEyMFx1YjRlNFx1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNTggXHVkNTY5XHVjNzc0IFx1Y2Q1Y1x1YzE4Y1x1Yzc3NFx1YjJlNC4gXHVhZGY4XHViN2YwIFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM1ZWNcdWI3ZmYgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0XHViYTc0IFx1YmFhOFx1YjQ1MCBtaW5pbXVtIHNwYW5uaW5nIGFyYm9yZXNjZW5jZVx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM4MTVcdWM4MTAgJE4kXHVhYzFjLCBcdWM3MjBcdWQ1YTUgXHVhYzA0XHVjMTIwICRNJFx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgREFHXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJE0kXHVhYzFjXHVjNzU4IFx1YWMwNFx1YzEyMFx1YzVkMCBcdWFjMDFcdWFjMDEgJDEkXHVjNzc0XHVjMGMxICRLJFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNThcdWI5N2MgXHViZDk5XHVjNzc0XHViMjk0ICRLXk0kXHVhYzAwXHVjOWMwXHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWIzMDBcdWQ1NzQsIG1pbmltdW0gc3Bhbm5pbmcgYXJib3Jlc2NlbmNlXHViOTdjIFx1YWQ2Y1x1YzEzMVx1ZDU1OFx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4IFx1ZDU2OVx1Yzc1OCBcdWFlMzBcdWIzMTNcdWFjMTJcdWM3NDQgJDk5OFxcLDI0NFxcLDM1MyRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWM1ZWNcdWI3N2MuIFx1YzkxMVx1YmNmNSBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWM3NGNcdWM1ZDAgXHVjNzIwXHVjNzU4XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWMxMzggXHVjODE1XHVjMjE4ICROLCBNLCBLJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAkTSRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCAkaSsxJFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YjczYlx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4ICRhX2ksIGJfaSRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWIyOTQgJGFfaSRcdWM1ZDBcdWMxMWMgJGJfaSRcdWI4NWMgXHVhYzAwXHViMjk0IFx1YzcyMFx1ZDVhNSBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTY4XHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFlMzBcdWIzMTNcdWFjMTJcdWM3NDQgJDk5OFxcLDI0NFxcLDM1MyRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzk4OSwgXHVhZTMwXHViMzEzXHVhYzEyXHVjNzc0IFx1YzExY1x1Yjg1Y1x1YzE4Y1x1Yzc3OCBcdWI0NTAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCAkYSQsICRiJFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVhZTMwXHVjNTdkXHViZDg0XHVjMjE4ICRcXGZyYWN7YX17Yn0kXHVjNzU4IFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MjAgXHViNTRjLCAkYiBcXGNkb3QgayBcXGVxdWl2IGEgXFxwbW9kezk5OFxcLDI0NFxcLDM1M30kXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWM3MjBcdWM3N2NcdWQ1NWMgXHVjODE1XHVjMjE4ICRrJCAoJDAgXFxsZSBrICZsdDsgOTk4XFwsMjQ0XFwsMzUzJClcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMSBcXGxlcSBOLCBNLCBLIFxcbGVxIDEwXjUgJDxcL2xpPlxyXG5cdDxsaT4kIE4tMSBcXGxlcSBNICQ8XC9saT5cclxuXHQ8bGk+XHViYWE4XHViNGUwICQxIFxcbGUgaSBcXGxlIE4kXHVjNWQwIFx1YjMwMFx1ZDU1OFx1YzVlYyAkIDEgXFxsZXEgYV9pICZsdDsgYl9pIFxcbGVxIE4kPFwvbGk+XHJcblx0PGxpPlx1YWUzMFx1Yzg3NCBEQUdcdWM1ZDBcdWMxMWMgMVx1YmM4OCBcdWM4MTVcdWM4MTBcdWM1ZDBcdWMxMWMgXHViMmU0XHViOTc4IFx1YmFhOFx1YjRlMCBcdWM4MTVcdWM4MTBcdWM1ZDAgXHViM2M0XHViMmVjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiRNID0gTi0xJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JE0gXFxsZXEgMTAsIEsgXFxsZXEgMiQ8XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPiROLCBNLCBLIFxcbGVxIDEwMDAkPFwvcD5cclxuIiwic3VidGFzazQiOiI8cD5cdWNkOTRcdWFjMDBcdWM4MDFcdWM3NzggXHVjODFjXHVjNTdkIFx1Yzg3MFx1YWM3NFx1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMzM4MDciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNaW5pbXVtIFNwYW5uaW5nIEFyYm9yZXNjZW5jZSIsImRlc2NyaXB0aW9uIjoiPHA+QW4gYXJib3Jlc2NlbmNlICRHID0gKFYsIEUpJCByb290ZWQgYXQgJHIkIGlzIGEgZGlyZWN0ZWQgZ3JhcGggdGhhdCBzYXRpc2ZpZXMgdGhlIGZvbGxvd2luZyBjb25kaXRpb246PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Rm9yIGV2ZXJ5IG90aGVyIHZlcnRleCAkdiQsIHRoZXJlIGV4aXN0cyBleGFjdGx5IG9uZSBkaXJlY3RlZCBwYXRoIGZyb20gJHIkIHRvICR2JC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5BIERBRyAoRGlyZWN0ZWQgQWN5Y2xpYyBHcmFwaCkgaXMgYSBkaXJlY3RlZCBncmFwaCB3aXRoIG5vIGN5Y2xlcy4gV2hlbiBlYWNoIGVkZ2UgaW4gdGhlIERBRyBpcyBhc3NpZ25lZCBhIHdlaWdodCwgYSBtaW5pbXVtIHNwYW5uaW5nIGFyYm9yZXNjZW5jZTxiPiA8XC9iPmlzIGRlZmluZWQgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5JdCBpcyBhbiBhcmJvcmVzY2VuY2Ugcm9vdGVkIGF0IHZlcnRleCA8c3BhbiBzdHlsZT1cImNvbG9yOiNjMDM5MmI7XCI+PHN0cm9uZz4kMSQ8XC9zdHJvbmc+PFwvc3Bhbj4uPFwvbGk+XHJcblx0PGxpPkl0IHNwYW5zIGFsbCB2ZXJ0aWNlcyBpbiB0aGUgREFHLjxcL2xpPlxyXG5cdDxsaT5BbW9uZyBhbGwgc3VjaCBhcmJvcmVzY2VuY2VzLCB0aGUgc3VtIG9mIHRoZSB3ZWlnaHRzIG9mIHRoZSBlZGdlcyB1c2VkIGlzIG1pbmltaXplZC4gSWYgdGhlcmUgYXJlIG11bHRpcGxlIHN1Y2ggYXJib3Jlc2NlbmNlcywgYWxsIG9mIHRoZW0gYXJlIGNvbnNpZGVyZWQgbWluaW11bSBzcGFubmluZyBhcmJvcmVzY2VuY2VzLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gYSBEQUcgd2l0aCAkTiQgdmVydGljZXMgYW5kICRNJCBkaXJlY3RlZCBlZGdlcy4gRWFjaCBvZiB0aGUgJE0kIGVkZ2VzIGNhbiBiZSBhc3NpZ25lZCBhIHdlaWdodCBiZXR3ZWVuICQxJCBhbmQgJEskLCByZXN1bHRpbmcgaW4gJEteTSQgcG9zc2libGUgYXNzaWdubWVudHMuIEZvciBlYWNoIHBvc3NpYmxlIGFzc2lnbm1lbnQgb2Ygd2VpZ2h0cywgY29uc2lkZXIgdGhlIG1pbmltdW0gc3Bhbm5pbmcgYXJib3Jlc2NlbmNlIHJvb3RlZCBhdCB2ZXJ0ZXggJDEkLiBDb21wdXRlIHRoZSBleHBlY3RlZCB0b3RhbCB3ZWlnaHQgb2YgdGhlIGVkZ2VzIHVzZWQgaW4gc3VjaCBhcmJvcmVzY2VuY2VzLCBhbmQgb3V0cHV0IHRoZSByZXN1bHQgbW9kdWxvICQ5OThcXCwyNDRcXCwzNTMkLiBOb3RlIHRoYXQgbXVsdGlwbGUgZWRnZXMgYmV0d2VlbiB0aGUgc2FtZSBwYWlyIG9mIHZlcnRpY2VzIG1heSBleGlzdC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRocmVlIGludGVnZXJzICROJCwgJE0kLCBhbmQgJEskLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgJE0kIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyAkYV9pJCBhbmQgJGJfaSQgaW5kaWNhdGluZyBhIGRpcmVjdGVkIGVkZ2UmbmJzcDtmcm9tIHZlcnRleCAkYV9pJCB0byB2ZXJ0ZXggJGJfaSQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBleHBlY3RlZCB2YWx1ZSBtb2R1bG8gJDk5OFxcLDI0NFxcLDM1MyQuPFwvcD5cclxuXHJcbjxwPlRoYXQgaXMsIGlmIHRoZSBleHBlY3RlZCB2YWx1ZSBjYW4gYmUgZXhwcmVzc2VkIGFzIGEgcmVkdWNlZCBmcmFjdGlvbiAkXFxmcmFje2F9e2J9JCBmb3IgdHdvIHBvc2l0aXZlIGNvcHJpbWUgaW50ZWdlcnMgJGEkIGFuZCAkYiQsIG91dHB1dCB0aGUgdW5pcXVlIGludGVnZXIgJGskIHN1Y2ggdGhhdCAkMCBcXGxlIGsgJmx0OyA5OThcXCwyNDRcXCwzNTMkIGFuZCAkYiBcXGNkb3QgayBcXGVxdWl2IGEgXFxwbW9kezk5OFxcLDI0NFxcLDM1M30kLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDEgXFxsZXEgTiwgTSwgSyBcXGxlcSAxMF41ICQ8XC9saT5cclxuXHQ8bGk+JCBOLTEgXFxsZXEgTSAkPFwvbGk+XHJcblx0PGxpPiQgMSBcXGxlcSBhX2kgJmx0OyBiX2kgXFxsZXEgTiQgZm9yIGV2ZXJ5Jm5ic3A7ICQxIFxcbGUgaSBcXGxlIE4kPFwvbGk+XHJcblx0PGxpPkluIHRoZSBnaXZlbiBEQUcsIHZlcnRleCAkMSQgY2FuIHJlYWNoIGV2ZXJ5IG90aGVyIHZlcnRleC48XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2sxIjoiPHA+JE0gPSBOIC0gMSQ8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPiRNIFxcbGUgMTAkLCAkSyBcXGxlIDIkPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD4kTiwgTSwgSyBcXGxlIDEsMDAwJDxcL3A+XHJcbiIsInN1YnRhc2s0IjoiPHA+Tm8gYWRkaXRpb25hbCBjb25zdHJhaW50cy48XC9wPlxyXG4ifV0=