Dynamic Connectivity in a Power-Based Graph

Farmer John has a set \(S = \{2, 3, 4, \dots, N\}\). For any two positive integers \(p, q\) in \(S\), they form a good pair if and only if \(p^k = q\) for some integer \(k \ge 2\). Consider each number in \(S\) as a node in an undirected graph. For every good pair, an undirected edge is added connecting the two nodes.

Farmer John performs \(Q\) operations, each of one of the following two types:

1. Given \(x\), query the size of the connected component containing node \(x\).
2. Given \(x\), remove \(x\) from \(S\) (and thereby remove the corresponding node from the graph).

Your task is to process these operations online. Note that if a node has been removed, then any query on that node should return 0.

inputFormat

The first line contains two integers \(N\) and \(Q\), where \(N \ge 2\) and \(Q\) is the number of operations.

The following \(Q\) lines each describe an operation in one of the following formats:

• 1 x: Query the size of the connected component containing node \(x\).
• 2 x: Remove node \(x\) from \(S\) and from the graph.

outputFormat

For each query operation (of type 1), output a single integer on a new line: the size of the connected component that contains \(x\) at the time of the query. If \(x\) has been removed, output 0.

sample

10 6
1 4
1 8
2 2
1 8
2 4
1 8

3
3
1
1