153. Day 4 PG. Hard Game

Hard Game

題目敘述

Jacob 和他的朋友 Bocaj 在一張圖 (graph) 上玩遊戲。 這張圖由 $N$ 塊餅乾及 $M$ 條連接餅乾的竹籤所組成。

特別地，這張圖的團數 (clique number) 與點著色數 (chromatic number) 都不超過 $2$。 (定義可參考提示)

遊戲是這樣進行的，兩個人輪流進行操作，每次操作包含兩個階段：

1. 若圖上沒有石頭，則可選任一個餅乾；否則要選一個與石頭相鄰的餅乾
2. 移除目前的所有石頭，並將階段 1 選中的餅乾變成石頭

當無法進行操作的時候遊戲結束；遊戲結束前最後一個操作的人獲勝。

假設 Jacob 先操作並且兩個人都採取最佳的策略，請問他第一步選哪些餅乾可以獲勝？

輸入說明

第一行有兩個正整數 $N, M$ 代表餅乾及竹籤的個數。餅乾的編號為 $1$ 到 $N$ 。

接下來有 $M$ 行，每一行有兩個正整數 $u, v$ ，表示有一條竹籤連接編號為 $u$ 及 $v$ 的餅乾。

• $ 2 \leq N \leq 10,000 $
• $ 1 \leq M \leq 300,000 $
• $ 1 \leq u,v \leq N $ 並且 $ u \neq v $

任兩個餅乾之間最多只有一隻竹籤。

輸出說明

請輸出 Jacob 可以選的餅乾個數。

範例輸入 1

3 2
1 2
1 3

範例輸出 1

2

範例輸入 2

5 4
1 2
3 1
4 3
5 2

範例輸出 2

3

提示

團 (clique) 是一個圖中，任兩個點之間都有邊的子圖。 一張圖的團數 (clique number) 是團的大小的最大值。

例如：正方形的團數是 $2$ ，加上一條對角線後是 $3$ ，再加另一條之後的團數是 $4$ 。

一張圖的點著色數是將圖中的頂點著色，並且相鄰的兩點顏色不能相同所需要的最少顏色個數。

例如：三色形的點著色數是 $3$ ，移除一條邊後是 $2$ ，再移餘一條邊之後的點著色數是 $1$ 。

出處

2017 程式大帝．改

Judge Setting

run-time limit: 1000 ms
memory limit: 256000000 byte
測資數量: 0