Problem:

分割統治

太郎さんと花子さんと次郎さんは3人で JAG 王国を統治している．JAG 王国には N 個の街が存在し，いくつかの街は双方向の道路で繋がっている．どの街からも別のすべての街へ 1 本以上の道路を経由して必ず辿り着くことができる．

ある日太郎さんと花子さんはとうとう仲違いを起こしてしまい，3 人で街を分担して統治することに決めた．しかし，あまりにも仲が悪くなりすぎてしまったため，太郎さんが統治している街と花子さんが統治している街が 1 本の道路で直接繋がっていることすら嫌がっている．そこで，以下の条件を満たすように統治する街を分担することにした．

太郎さんが統治する街と花子さんが統治する街からなる任意のペアは，直接道路で繋がっていない．これは太郎さんと花子さんの仲がめちゃくちゃ悪いからである．

同じ人に統治されている街同士も直接道路で繋がっていない．これは，そんな中でも他者の統治下の経由を義務付けることで外交を促すためである．

太郎さんの統治する街の総数と花子さんが統治する街の総数は同じでなければならない．これは総数を等しくしないと太郎さんと花子さんの仲がさらにめちゃくちゃ悪くなりそうだからである．ここで，次郎さんはとても心が広いので，次郎さんが統治する街の総数はいくつでもよい．

以上の条件を満たすような分担であれば，3 人は納得して統治することができ，たとえ誰かの統治する街が 0 個であっても文句はない．このとき，太郎さんが統治する街の総数 (=花子さんが統治する街の総数) としてあり得る数をすべて列挙するプログラムを作成せよ．

Input

入力は複数のデータセットからなる．
データセットの数は最大で 50 である．
各データセットは，次の形式で表される．

N M
u1 v1
...
uM vM

1 行目は 2 つの整数 N (2 ≤ N ≤ 103) と M (1 ≤ M ≤ 103) からなり，それぞれ街の数と道路の数を表す．続く M 行のうち i 行目は 2 つの整数 ui と vi (1 ≤ ui < vi ≤ N) からなり，i 番目の道路が街 ui と 街 vi を双方向に繋いでいることを表す．ここで，どの街からも別のすべての街へ 1 本以上の道路を経由して必ず辿り着くことができることが保証される．また，同じ街のペアを結ぶ道路が複数与えられることはない．すなわち，すべての 1 ≤ i < j ≤ M について (ui, vi) &ne; (uj, vj) を満たす．

入力の終わりは 2 つのゼロからなる行で表される．

Output

各データセットについて，太郎さんが統治する街の総数として考えられる数が K 通りあるとき，まず 1 行目に K を出力し，その後，あり得る総数を 1 行に 1 つずつ昇順で出力せよ．

Sample Input

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

Output for the Sample Input

2
1
2
0
0
1
1
1
1



Sample input:
6 7
1 2
1 4
2 3
2 5
3 4
4 5
4 6
2 1
1 2
3 3
1 2
1 3
2 3
4 3
1 2
2 3
3 4
5 4
1 2
2 3
3 4
4 5
0 0


Sample output:
2
1
2
0
0
1
1
1
1

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    while True:
        N, M = map(int, input().split())
        if N == 0:
            break
        path = [[False] * N for i in range(N)]
        for i in range(M):
            u, v = map(int, input().split())
            u -= 1; v -= 1;
            path[u][v] = True
            path[v][u] = True

        d = [-1] * N
        d[0] = 0
        q = [0]
        while len(q) > 0:
            now = q.pop(0)
            for i in range(N):
                if path[now][i] and d[i] == -1:
                    q.append(i)
                    d[i] = d[now] + 1
        ok = True
        for i in range(1, N):
            for j in range(i+1, N):
                if path[i][j] and d[i] == d[j]:
                    ok = False
                    break
            if not ok:
                break
        if not ok:
            print(0)
        else:
            num = 0
            for i in range(N):
                if d[i]&1:
                    num += 1
            if N&1:
                print(1)
                if num&1:
                    print((N-num)//2)
                else:
                    print(num//2)
            else:
                if num&1:
                    print(0)
                else:
                    if N//2 == num:
                        print(1)
                        print(num//2)
                    else:
                        print(2)
                        tmp = min(num, N-num)
                        print(tmp//2)
                        print((N-tmp)//2)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)

def dfs(graph, visited, x, c):
  visited[x] = c
  for nx in graph[x]:
    if visited[nx] == c:
      return False
    if visited[nx] == 0 and not dfs(graph, visited, nx, -c):
      return False
  return True


while True:
  n, m = list(map(int, input().split()))
  if n==0:
    break

  graph = defaultdict(list)
  visited = [0 for i in range(n+1)]
  for i in range(m):
    u, v = list(map(int, input().split()))
    graph[u].append(v)
    graph[v].append(u)

  f = dfs(graph, visited, 1, 1)
  if f == False:
    print(0)
  else:
    ans1, ans2 = 0, 0
    for i in range(1, n+1):
      if visited[i]>0:
        ans1 += 1
      elif visited[i]<0:
        ans2 += 1
    ans = set()
    if ans1%2==0:
      ans.add(ans1//2)
    if ans2%2==0:
      ans.add(ans2//2)
    print(len(ans))
    for e in sorted(ans):
      print(e)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(5000)

def dfs(x):
    global ng, parity
    for v in adj[x]:
        if parity[v] == parity[x]:
            ng = True
            return
        elif parity[v] < 0:
            parity[v] = 1^parity[x]
            dfs(v)
    return

while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    adj = [[] for _ in range(n)]
    parity = [-1 for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)
    ng = False
    parity[0] = 0
    dfs(0)
    if ng:
        print(0)
        continue
    ans = []
    zero = parity.count(0)
    if zero%2 == 0:
        ans.append(zero//2)
    if (n-zero)%2 == 0 and zero*2 != n:
        ans.append((n-zero)//2)
    ans.sort()
    print(len(ans))
    if ans:
        print(*ans, sep="\n")

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    while 1:
        n,m = LI()
        if n == 0 and m == 0:
            break
        v = [[] for i in range(n)]
        for i in range(m):
            a,b = LI()
            a -= 1
            b -= 1
            v[a].append(b)
            v[b].append(a)
        bfs_map = [1 for i in range(n)]
        bfs_map[0] = 0
        f = [0 for i in range(n)]
        q = deque()
        q.append(0)
        fl = 1
        while q:
            if not fl:break
            x = q.popleft()
            for y in v[x]:
                if bfs_map[y]:
                    bfs_map[y] = 0
                    f[y] = (1-f[x])
                    q.append(y)
                else:
                    if f[y] == f[x]:
                        print(0)
                        fl = 0
                        break
        if fl:
            ans = []
            k = sum(f)
            if k%2 == 0:
                ans.append(k//2)
            k = len(f)-sum(f)
            if k%2 == 0:
                ans.append(k//2)
            ans = list(set(ans))
            ans.sort()
            print(len(ans))
            for i in ans:
                print(i)
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    A()