CF1499G Graph Coloring

Description

You are given a bipartite graph consisting of $ n_1 $ vertices in the first part, $ n_2 $ vertices in the second part, and $ m $ edges, numbered from $ 1 $ to $ m $ . You have to color each edge into one of two colors, red and blue. You have to minimize the following value: $ \sum \limits_{v \in V} |r(v) - b(v)| $ , where $ V $ is the set of vertices of the graph, $ r(v) $ is the number of red edges incident to $ v $ , and $ b(v) $ is the number of blue edges incident to $ v $ . Sounds classical and easy, right? Well, you have to process $ q $ queries of the following format: - $ 1 $ $ v_1 $ $ v_2 $ — add a new edge connecting the vertex $ v_1 $ of the first part with the vertex $ v_2 $ of the second part. This edge gets a new index as follows: the first added edge gets the index $ m + 1 $ , the second — $ m + 2 $ , and so on. After adding the edge, you have to print the hash of the current optimal coloring (if there are multiple optimal colorings, print the hash of any of them). Actually, this hash won't be verified, you may print any number as the answer to this query, but you may be asked to produce the coloring having this hash; - $ 2 $ — print the optimal coloring of the graph with the same hash you printed while processing the previous query. The query of this type will only be asked after a query of type $ 1 $ , and there will be at most $ 10 $ queries of this type. If there are multiple optimal colorings corresponding to this hash, print any of them. Note that if an edge was red or blue in some coloring, it may change its color in next colorings. The hash of the coloring is calculated as follows: let $ R $ be the set of indices of red edges, then the hash is $ (\sum \limits_{i \in R} 2^i) \bmod 998244353 $ . Note that you should solve the problem in online mode. It means that you can't read the whole input at once. You can read each query only after writing the answer for the last query. Use functions fflush in C++ and BufferedWriter.flush in Java languages after each writing in your program.

Input Format

N/A

Output Format

N/A