0 Judge
Code: 0
Jacob 和他的朋友 Bocaj 在一張圖 (graph) 上玩遊戲。 這張圖由 $N$ 塊餅乾及 $M$ 條連接餅乾的竹籤所組成。
特別地,這張圖的團數 (clique number) 與點著色數 (chromatic number) 都不超過 $2$。 (定義可參考提示)
遊戲是這樣進行的,兩個人輪流進行操作,每次操作包含兩個階段:
當無法進行操作的時候遊戲結束;遊戲結束前最後一個操作的人獲勝。
假設 Jacob 先操作並且兩個人都採取最佳的策略,請問他第一步選哪些餅乾可以獲勝?
第一行有兩個正整數 $N, M$ 代表餅乾及竹籤的個數。餅乾的編號為 $1$ 到 $N$ 。
接下來有 $M$ 行,每一行有兩個正整數 $u, v$ ,表示有一條竹籤連接編號為 $u$ 及 $v$ 的餅乾。
任兩個餅乾之間最多只有一隻竹籤。
請輸出 Jacob 可以選的餅乾個數。
3 2
1 2
1 3
2
5 4
1 2
3 1
4 3
5 2
3
團 (clique) 是一個圖中,任兩個點之間都有邊的子圖。 一張圖的團數 (clique number) 是團的大小的最大值。
例如:正方形的團數是 $2$ ,加上一條對角線後是 $3$ ,再加另一條之後的團數是 $4$ 。
一張圖的點著色數是將圖中的頂點著色,並且相鄰的兩點顏色不能相同所需要的最少顏色個數。
例如:三色形的點著色數是 $3$ ,移除一條邊後是 $2$ ,再移餘一條邊之後的點著色數是 $1$ 。
2017 程式大帝.改