You are given an undirected connected graph *G* consisting of *n* vertexes and *n* edges. *G* contains no self-loops or multiple edges. Let each edge has two states: on and off. Initially all edges are switched off.

You are also given *m* queries represented as (*v*, *u*) — change the state of all edges on the shortest path from vertex *v* to vertex *u* in graph *G*. If there are several such paths, the lexicographically minimal one is chosen. More formally, let us consider all shortest paths from vertex *v* to vertex *u* as the sequences of vertexes *v*, *v*<sub class="lower-index">1</sub>, *v*<sub class="lower-index">2</sub>, ..., *u*. Among such sequences we choose the lexicographically minimal one.

After each query you should tell how many connected components has the graph whose vertexes coincide with the vertexes of graph *G* and edges coincide with the switched on edges of graph *G*.
The first line contains two integers *n* and *m* (3 ≤ *n* ≤ 10<sup class="upper-index">5</sup>, 1 ≤ *m* ≤ 10<sup class="upper-index">5</sup>). Then *n* lines describe the graph edges as *a* *b* (1 ≤ *a*, *b* ≤ *n*). Next *m* lines contain the queries as *v* *u* (1 ≤ *v*, *u* ≤ *n*). 

It is guaranteed that the graph is connected, does not have any self-loops or multiple edges.
def pairs_of_numbers(n, k, arr):
    # Create a dictionary to store occurrences of each number
    num_dict = {}
    for num in arr:
        num_dict[num] = num_dict.get(num, 0) + 1

    count = 0
    for num in arr:
        # Calculate its pair using XOR operation
        pair_num = num ^ k

        # Check if the pair exists and if the number is less than or equal to its pair
        if pair_num in num_dict and num <= pair_num:
            # If the number and its pair are the same, we divide the count by 2 
            # because each pair will be counted twice
            if num == pair_num:
                count += num_dict[num] // 2
            else:
                count += min(num_dict[num], num_dict[pair_num])

    return count

# Sample Input
n, k = map(int, input().split())
arr = list(map(int, input().split()))

# Output the result
print(pairs_of_numbers(n, k, arr))
