DZY loves chemistry, and he enjoys mixing chemicals. DZY has n chemicals, and m pairs of…
- User
DZY loves chemistry, and he enjoys mixing chemicals.
DZY has n chemicals, and m pairs of them will react. He wants to pour these chemicals into a test tube, and he needs to pour them in one by one, in any order.
Let's consider the danger of a test tube. Danger of an empty test tube is 1. And every time when DZY pours a chemical, if there are already one or more chemicals in the test tube that can react with it, the danger of the test tube will be multiplied by 2. Otherwise the danger remains as it is.
Find the maximum possible danger after pouring all the chemicals one by one in optimal order. Input
The first line contains two space-separated integers n and m .
Each of the next m lines contains two space-separated integers xi and yi (1 ≤ xi < yi ≤ n). These integers mean that the chemical xi will react with the chemical yi. Each pair of chemicals will appear at most once in the input.
Consider all the chemicals numbered from 1 to n in some order.
Output
Print a single integer — the maximum possible danger.
Examples
Input
1 0
Output
1
Input
2 1 1 2
Output
2
Input
3 2 1 2 2 3
Output
4
Note
In the first sample, there's only one way to pour, and the danger won't increase.
In the second sample, no matter we pour the 1st chemical first, or pour the 2nd chemical first, the answer is always 2.
In the third sample, there are four ways to achieve the maximum possible danger: 2-1-3, 2-3-1, 1-2-3 and 3-2-1 (that is the numbers of the chemicals in order of pouring).
Assistant
We need to parse the problem carefully. We have n chemicals. There are m pairs that can react. We pour chemicals one by one in some order. Initially tube empty, danger=1. Each time we pour a chemical, if there is already at least one chemical in the tube that can react with it, then danger = danger * 2. Otherwise, danger remains unchanged.
We need to find the maximum possible danger after pouring all n chemicals, by choosing the optimal ordering.
Observations: Danger is multiplied by 2 each time a chemical we add has at least one neighbor (already present) that it can react with. So the danger final = 2^{k} where k is the number of times such a multiplication occurs. So we need to maximize the count k of times we get a reaction (i.e., when a poured chemical has at least one neighbor already present). Since we can choose order arbitrarily, we want as many pours as possible to cause a multiplication.
Note: The condition is "if there are already one or more chemicals in the test tube that can react with it". So for a chemical v, if among the already poured chemicals, there exists any u such that (u,v) is a reacting pair, then danger doubles.
Thus, the only way a pour does not cause doubling is if none of its neighbors (in the reaction graph) have been poured yet. That is, it is the first among its connected component? Not exactly.
We can think of the graph: vertices = chemicals, edges = reacting pairs. The pouring order is a permutation. For each vertex v, when it is added, if any neighbor of v appears before v in the order, then it triggers a doubling. Otherwise, if all neighbors appear after v, then no doubling.
Thus, the total number of doublings is equal to the number of vertices that have at least one neighbor earlier in the order, i.e., vertices that are not the first in their connected component's BFS/DFS order? But note that a component might have multiple vertices that have no earlier neighbor if we order carefully? Let's examine.
In a connected component, if we order the vertices in a sequence, for each vertex v (except the first vertex in the component) we can ensure that at least one neighbor appears earlier? In a connected component, if we order the vertices in a topological order of a spanning tree, then except the root (first), each vertex can have its parent earlier, so that would cause a doubling for all except one per component. However, can we get a component where multiple vertices have no earlier neighbor? Suppose we have a component with vertices A, B, C where edges: A-B, B-C. If we order as A, C, B. When we add A: first, no neighbor yet => no double. When we add C: neighbors are B only? B not added yet => no neighbor => no double. When we add B: neighbors are A and C, both already present => double. So in this order, only one double? Actually, we got doubling only for B, so k=1. But we could have gotten doubling for two vertices? If order A, B, C: A first no double; B has neighbor A earlier => double; C has neighbor B earlier => double => k=2. So order matters.
The maximum possible k in a component of size s? Since we start with danger 1, each pour can potentially double if added after at least one neighbor. The first pour of the component obviously can't double because tube empty (or maybe if there are chemicals from other components? But note: if there are multiple components, they are independent in the sense that edges only exist within components. So if we start with a chemical from component A, it has no neighbor yet, so no double. Later, when we pour a chemical from component B, if it has no neighbors from its own component already poured, but could it have neighbors from component A? No, because there is no edge between components. So the condition only depends on neighbors within the same component. Thus, the components are independent: the total number of doublings is sum over components of the number of doublings achieved within that component, because the presence of chemicals from other components does not affect whether a chemical has a reacting neighbor (since there is no cross-edge). So we can treat each connected component separately and sum the maximal possible doublings in each component.
For a connected component with v vertices (size), what is the maximum number of vertices that can have at least one neighbor earlier? Equivalent to: we want to order the vertices of the component to maximize the count of vertices that are not the first in the order in terms of having at least one earlier neighbor. But note: Could a vertex have no earlier neighbor even if it is not the first? In a connected graph, if we order vertices arbitrarily, it's possible that a vertex (except the first) has all its neighbors after it. Is that possible? For a vertex v that appears at position p>1, if none of its neighbors appear before p, then v is isolated from earlier vertices. But since the graph is connected, there must be some path from v to earlier vertices, but if all immediate neighbors are after, then there is no direct neighbor earlier, but perhaps there is a neighbor that is after, and that neighbor might have earlier neighbors, etc. But for the condition, we only care about direct neighbors. So it's possible for a vertex (except the first) to have all neighbors after it, as long as it's not adjacent to any earlier vertex. For example, a path of length 2: A-B-C. In order A, C, B: C's only neighbor is B, which appears after; so C has no earlier neighbor. So it's possible. So maximum doublings might be less than v-1? Actually, can we achieve doublings for all vertices except one? In a tree, we can root it and do a BFS ordering: parent before children. Then each child will have its parent earlier, so all except the root double. That yields v-1 doublings. But is that always achievable? For any connected graph, we can take a spanning tree, and order vertices in a linear extension such that each vertex (except root) appears after its parent. That gives v-1 doublings. So maximum is at least v-1. Could we get v doublings? The first vertex poured in the whole process has no neighbor because tube empty, so it can't double. However, if we consider multiple components, the first vertex of the first component also can't double. But maybe if we pour a component after some other component, the first vertex of the second component might have neighbors? But there is no cross-edge, so still no neighbor from its own component, but could it have neighbors from other components? No, because edges only between chemicals that react. So it cannot react with chemicals from other components, so still no neighbor that can react. Therefore, the first chemical poured from each component cannot cause a double, because at the moment it's poured, there are no chemicals from its component yet (assuming we pour components sequentially). But what if we interleave components? For the first chemical of a component, when it's poured, there may be chemicals from other components already in the tube, but they are not reacting partners, so condition "if there are already one or more chemicals in the test tube that can react with it" only checks for reacting pairs. Since there are no edges to other components, the condition is false. So the first chemical of each component never doubles, regardless of order of components. So each connected component contributes at most (size - 1) doublings. And we can achieve size-1 by ordering within the component as a tree order (e.g., BFS from some root). So maximum total doublings = sum over components (size_i - 1) = n - (number of connected components). Then final danger = 2^{n - (number of components)}.
Let's test with examples.
Example 2: n=2, m=1, edge (1,2). Graph is one component, size=2. So danger = 2^{2-1}=2. correct.
Example 3: n=3, m=2, edges (1,2),(2,3). Graph is connected (one component). Danger=2^{3-1}=4. correct.
Example 1: n=1, m=0 -> components=1, size=1, danger=2^{0}=1. correct.
What about a case with multiple components? e.g., n=4, m=0 -> 4 isolated vertices, each component size=1, total components=4, danger=2^{4-4}=2^0=1. Indeed, no reaction ever, danger stays 1. That makes sense: with no edges, no chemical has any neighbor, so never double.
Another test: n=4, edges: (1,2),(3,4) two components each of size 2. Then max danger = 2^{(2-1)+(2-1)} = 2^2 = 4. Let's try to construct order: Component A: 1,2. Component B: 3,4. We need to pour all four. If we pour 1 (no double), then 2 (double, because 1 reacts), then 3 (no double, because no neighbor from its component yet? But tube contains 1,2, but they don't react with 3), then 4 (double, because 3 already). So total double count=2, danger=4. Could we do better by interleaving? Suppose order: 1,3,2,4. When we pour 1: no double. 3: no double (no neighbor). 2: neighbor 1 already? Yes, 1 reacts with 2, so double. 4: neighbor 3 already? Yes, double. So also 2 doubles. So maximum=2. Works.
What about a component with a cycle? For a triangle (3 vertices all connected). size=3. Our formula gives 2^{3-1}=4. Can we achieve 2 doubles? Let's test: order 1,2,3. 1: no double. 2: neighbor 1 => double. 3: neighbors 1 and 2, at least one earlier => double. So two doubles, danger=4. Could we get 3 doubles? The first chemical cannot double, so max is 2. So correct.
Thus, the answer is simply 2^{n - c}, where c is number of connected components in the graph (including isolated vertices). But careful: is there any subtlety about multiple edges? No, each pair at most once. Also note that components are defined based on the reaction graph. Since there are no self-reactions, each vertex is a node.
But is it always achievable to get exactly size_i -1 doublings per component? Yes, by ordering such that for each component we take a spanning tree and do a DFS order (or any order where each vertex except the root has at least one neighbor earlier). But must ensure that within each component, the first vertex of that component is poured at a time when there are no other chemicals from that component (obviously) but may have other components. That doesn't affect the condition. So we can simply pour all chemicals from one component in a tree order, then move to next component. That yields for each component, the first vertex contributes 0 doubles, the rest contribute 1 double each.
But is there any scenario where we could get more than size-1 per component? Could the first vertex of a component double because of a chemical from another component that somehow reacts? No, edges are only given; cross-component edges don't exist. So no.
Thus, answer = 2^{n - number_of_components}.
Implementation: read n,m, build adjacency list? We only need number of connected components. Use DSU (union-find) to count components. Or BFS/DFS. Since n up to? Not given in problem statement but typical constraints: n up to maybe 10^5? m up to 10^5? We should use efficient methods. The problem statement only says n and m (maybe up to 50? But to be safe, we can handle up to 10^5 or 10^6). DSU is straightforward.
Initialize DSU with n elements. For each edge (x,y), union(x-1,y-1) (or 1-indexed with DSU). After processing all edges, count distinct sets: number of components = number of roots. Then answer = 1 << (n - components) ?? But n - components could be up to n, which could be large (like 50? maybe 10^5). 2^(n - components) can be huge; the output should be an integer. But the problem expects possibly large integer? Usually in such problems, answer can be large, but they expect to output the exact integer (maybe up to 2^50? But could be up to 2^(10^5) which is astronomically huge; typical Codeforces problems require outputting such huge numbers as a standard integer? Usually they ask to print a single integer, and constraints are such that answer fits in 64-bit? Let's check typical problem: "DZY loves chemistry" is a Codeforces problem? I recall a Codeforces problem: CF 445A? Actually, I think it's Codeforces Round #FF? There is problem "DZY loves chemistry" (CF 444A? Not sure). I think it's Codeforces 445B? Actually, I recall a problem "DZY loves Chemistry" from Codeforces Round #... The typical solution is indeed 2^(n - number of connected components). And n can be up to 50? Or maybe up to 10^5? I'd need to check memory. Let me search mental database: There is a problem "DZY loves Chemistry" on Codeforces with ID 445B? Wait, 445B is "DZY loves chemistry"? No, 445B is "DZY loves chemistry" maybe. Let me recall: I think it's Codeforces Round #254 Div2 problem "DZY loves Chemistry" (maybe 445A?). Actually, I remember a problem: "DZY loves chemistry" where the answer is 2^(n - number_of_components). And constraints: n <= 50, m <= n(n-1)/2. Or perhaps n <= 50? Because 2^50 fits in 64-bit? 2^50 ≈ 1e15, fits in 64-bit. But 2^1000 doesn't. Let's see typical problems: There is a problem "DZY loves Chemistry" with n up to 50, and it's easy to compute using bit operations. But I'm not sure. Better check the problem statement: It says "The first line contains two space-separated integers n and m ." There's an image? Possibly it's from some contest. But many such problems have small constraints. However, I've seen a problem "DZY loves Chemistry" where n ≤ 50, and answer fits in 64-bit. But there is also "DZY loves Chessboard" etc. Let's search mental: On Codeforces, there's "DZY loves Chemistry" (problem 445B). Actually, I'll try to recall: The handle "DZY" is a Codeforces user. Many problems titled "DZY loves ...". I think 445B is "DZY loves Chemistry". I'm not 100% sure. I can quickly check: Codeforces Round 254 Div2 includes problems: A - DZY loves Chessboard, B - DZY loves Chemistry, C - DZY loves Physics, etc. Yes, I think that's correct: Round #254 (Div. 2): A. DZY Loves Chessboard, B. DZY Loves Chemistry, C. DZY Loves Physics, D. DZY Loves ... So I think the problem we are dealing with is indeed Codeforces 445B? Wait, I'm mixing numbers. Actually, Round #254 corresponds to problems 445? I think round #254 has problems 445A, 445B, etc. Yes, Codeforces Round #254 (Div. 2) problem B: "DZY Loves Chemistry". So let's look up constraints: In Codeforces 445B, constraints: n ≤ 50, m ≤ n(n-1)/2. Indeed, many solutions compute 2^(n - number_of_components). So answer fits in 64-bit because n ≤ 50 => 2^50 ~ 1e15, fits in long long.
But I should be careful: The problem statement given in the prompt doesn't specify constraints, but the examples match that problem. It's safe to assume n is not huge (maybe up to 50). But even if larger, we can compute using big integers? The problem expects a single integer, possibly large, but typical Codeforces problem doesn't use big integers for Div2 B. So likely n ≤ 50.
Nevertheless, I can implement using Python which handles big integers automatically. So we can just compute 2**(n - components) and print.
But we need to be careful about the condition "if there are already one or more chemicals in the test tube that can react with it, danger multiplies by 2". That's exactly as described.
Thus solution: use DSU to find number of connected components. Then answer = 1 << (n - components) for languages with big integers, or pow(2, n - components) in Python.
Let's write solution in Python.
Implementation steps:
- Read n, m.
- Initialize parent array of size n, initially each i parent[i]=i.
- Define find and union.
- For each of m lines: read x, y (1-indexed). Union(x-1, y-1).
- After all unions, count number of distinct roots: set of find(i) for i in range(n).
- components = len(set).
- answer = 2**(n - components).
- print(answer)
Edge cases: m may be 0 => each node isolated => components = n => answer = 2**0 = 1.
Time complexity: O(n + m * α(n)).
Alternative: BFS/DFS on adjacency list. But DSU simpler.
But careful: The graph might have loops? Input says xi < yi, so no self loops. So fine.
Thus, answer is straightforward.
But is there any twist? Could we get more than n - components doublings? For example, if a component is such that a vertex could double multiple times? No, each pour only multiplies once. So the total number of doublings is at most number of pours where condition holds. Since there are n pours, maximum doublings is n - number_of_components as argued.
But check: Could we arrange that the first chemical of a component also doubles because there is a reaction with some chemical from another component? No, as no edges between components. So it's impossible.
Thus answer stands.
I'll produce final answer.
But need to consider: the danger is initially 1 and gets multiplied by 2 each time. So final danger = 2^{number_of_times_doubled}. So answer = 2^{n - c}.
Now we can code.
But wait, is there any nuance about the fact that when we pour a chemical, if there is already one or more chemicals that can react with it, we multiply by 2. Could it be that there are multiple such chemicals, but we still multiply only once? Yes, it's just "the danger will be multiplied by 2", not multiplied by number of reacting chemicals. So each pour contributes at most one factor of 2.
Thus fine.
So final solution.
Let's test with some custom cases:
Case: n=5, edges: (1,2),(2,3),(4,5). So components: {1,2,3} size3, {4,5} size2, plus? Actually we have 5 vertices, components: one of size3, one of size2. So components=2, n - components = 3, answer = 2^3=8. Can we achieve 3 doublings? Order: 1,2,3,4,5: doubles at 2,3,5? Actually: 1 none, 2 double (with 1), 3 double (with 2 or 1), 4 none (no neighbor from its component), 5 double (with 4) => total 3 doubles => 2^3=8. Or we could interleave: 1,4,2,5,3: 1 none, 4 none, 2 double (neighbor 1), 5 double (neighbor 4), 3 double (neighbors 1,2) -> 3 doubles. Works.
Case: n=3, edges: none => components=3, answer=2^0=1.
Case: n=4, edges: (1,2),(1,3),(1,4) star. components=1, answer=2^3=8. Order: 1,2,3,4: 1 none, 2 double (1), 3 double (1), 4 double (1) => 3 doubles => 8. Works.
Thus correct.
Now, we need to output the answer as integer, no mod.
So Python code:
def solve(): import sys data = sys.stdin.read().strip().split() if not data: return it = iter(data) n = int(next(it)) m = int(next(it)) parent = list(range(n)) rank = [0]*n # optional for union by rank
def find(x): while parent[x]!=x: parent[x] = parent[parent[x]] x = parent[x] return x def union(x,y): rx, ry = find(x), find(y) if rx==ry: return # union by rank if rank[rx] < rank[ry]: parent[rx] = ry elif rank[rx] > rank[ry]: parent[ry] = rx else: parent[ry] = rx rank[rx] += 1 for _ in range(m): x = int(next(it))-1 y = int(next(it))-1 union(x,y) roots = set() for i in range(n): roots.add(find(i)) comp = len(roots) ans = 1 << (n - comp) # use shift; careful if n-comp large, Python handles big ints # Alternatively: ans = 2**(n-comp) print(ans)if name == "main": solve()
But note: Using shift works for Python ints.
But we can also simply use 2**(n-comp). I'll use shift.
Now, ensure that we handle the case where n-comp could be huge? but Python fine.
But if constraints are like n up to 10^5, answer would be astronomically large with about 30k digits, which is still printable? Possibly the problem expects a big integer output. However, typical Codeforces problem with such large output would require modulo or something. But since the problem statement doesn't mention modulo, we can output the full integer. Python can handle it. So it's okay.
I think solution is correct.
But wait, I'm reading the note: "Consider all the chemicals numbered from 1 to n in some order." That just says the chemicals are numbered. So fine.
Thus final answer.
Now write final explanation.
We'll produce final output as code in python.
But the problem may require using 64-bit if n <= 50, but Python is fine.
Thus final answer. ```python
import sys
def solve() -> None: data = sys.stdin.read().strip().split() if not data: return it = iter(data) n = int(next(it)) m = int(next(it))
parent = list(range(n)) rank = [0] * n def find(x: int) -> int: # path compression while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x def union(x: int, y: int) -> None: rx = find(x) ry = find(y) if rx == ry: return # union by rank if rank[rx] < rank[ry]: parent[rx] = ry elif rank[rx] > rank[ry]: parent[ry] = rx else: parent[ry] = rx rank[rx] += 1 for _ in range(m): x = int(next(it)) - 1 y = int(next(it)) - 1 union(x, y) components = len({find(i) for i in range(n)}) answer = 1 << (n - components) # same as 2**(n - components) print(answer)if name == "main": solve()