Problem : 157 - Dicing

Special Judge

Problem Statistics

Solved Member: 6　　Submission: 37　　User Tried: 7

Statement:

波蘭選訓營的人無聊的時候很喜歡玩一種叫做 Dicing 的遊戲，遊戲的內容是這樣的，由 n 個人和 m 場比賽所組成，n 個人分別由 1 標號到 n，每場比賽固定會有兩個人參加，這兩個人之中會產出一個勝者。

選訓營的人會統計出所有人勝利的場數，並選出勝利數最多的「數個」人當做冠軍。

你想知道，若想成為冠軍最少需要贏多少場才有可能。

Input:Output:

第一行有兩個數字 n,m(1 ≤ n,m ≤ 10000)，代表人數以及比賽場數。
第二行開始 m 行每行有兩個數字 Ai,Bi，代表第 i 場比賽是編號 Ai 的人跟編號 Bi 的人比。

請輸出一個數字，代表最少需要贏多少次才有可能成為冠軍。
後面 m 行請輸出一個數字，0或1，若 1 代表第 i 場比賽贏的人是 Ai，輸出 0 代表這場比賽是 Bi贏。
若存在多組解請隨便輸出一組。

Sample Input:Sample Output:

4 4
1 2
1 3
1 4
1 2

1
0
0
0
1

HINT:

不要被測資範圍侷限想法...這題複雜度很高，看起來會TLE的解可能是正解。

Source:

POI 12 Stage 2

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	3000ms	32768kb
1-ocen	3000ms	32768kb
1-1	3000ms	32768kb	7
1-2	3000ms	32768kb
2-ocen	3000ms	32768kb
2-1	3000ms	32768kb	7
2-2	3000ms	32768kb
3-ocen	3000ms	32768kb
3-1	3000ms	32768kb	7
3-2	3000ms	32768kb
4-ocen	3000ms	32768kb
4-1	3000ms	32768kb	7
4-2	3000ms	32768kb
5-1	3000ms	32768kb	7
5-2	3000ms	32768kb
6-1	4000ms	32768kb	7
6-2	3000ms	32768kb
7-1	3000ms	32768kb	7
7-2	3000ms	32768kb
8-1	3000ms	32768kb	7
8-2	3000ms	32768kb
9-1	3000ms	32768kb	7
9-2	3000ms	32768kb
10-1	3000ms	32768kb	7
10-2	3000ms	32768kb
11-1	3000ms	32768kb	7
11-2	3000ms	32768kb
12-1	25000ms	32768kb	7
12-2	25000ms	32768kb
13	25000ms	32768kb	8
14	25000ms	32768kb	8