from collections import defaultdict from Queue import Queue def flip(n): if n == 1: return 2 return 1 def main(): graph = defaultdict(list) numEdges = input() for i in xrange(numEdges): u,v = raw_input().split() graph[u].append(v) graph[v].append(u) print bfs(graph) def bfs(graph): visited = defaultdict(int) visited[graph.keys()[0]] = 1 q = Queue() q.put(graph.keys()[0]) while not q.empty(): node = q.get() value = visited[node] print node, value for neighbor in graph[node]: if visited[neighbor] == 0: visited[neighbor] = flip(value) q.put(neighbor) elif visited[neighbor] == value: return False return True if __name__ == '__main__': main()