Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

A smile house is created to raise the mood. It has n rooms. Some of the rooms are…

  1. User

    A smile house is created to raise the mood. It has n rooms. Some of the rooms are connected by doors. For each two rooms (number i and j), which are connected by a door, Petya knows their value cij — the value which is being added to his mood when he moves from room i to room j.

    Petya wondered whether he can raise his mood infinitely, moving along some cycle? And if he can, then what minimum number of rooms he will need to visit during one period of a cycle? Input

    The first line contains two positive integers n and m (), where n is the number of rooms, and m is the number of doors in the Smile House. Then follows the description of the doors: m lines each containing four integers i, j, cij и cji (1 ≤ i, j ≤ n, i ≠ j, - 104 ≤ cij, cji ≤ 104). It is guaranteed that no more than one door connects any two rooms. No door connects the room with itself.

    Output

    Print the minimum number of rooms that one needs to visit during one traverse of the cycle that can raise mood infinitely. If such cycle does not exist, print number 0.

    Examples

    Input

    4 4 1 2 -10 3 1 3 1 -10 2 4 -10 -1 3 4 0 -3

    Output

    4

    Note

    Cycle is such a sequence of rooms a1, a2, ..., ak, that a1 is connected with a2, a2 is connected with a3, ..., ak - 1 is connected with ak, ak is connected with a1. Some elements of the sequence can coincide, that is, the cycle should not necessarily be simple. The number of rooms in the cycle is considered as k, the sequence's length. Note that the minimum possible length equals two.

  2. DeepSeek Assistant

    We are given a directed graph? Actually the input describes edges between rooms i and j with two values: cij and cji. That indicates that there is a door connecting rooms i and j, and moving from i to j adds cij to mood, moving from j to i adds cji. So it's essentially a directed graph with two directed edges for each undirected door (except possibly if values are such that we only consider positive? but no, they could be negative). So we have a directed graph with n vertices and up to 2*m directed edges (since each door yields two directed arcs). We need to find if there exists a cycle (directed cycle) such that the sum of the edge costs along the cycle is positive. That is, a cycle with total positive weight. And among all such cycles (that have positive total weight), we want the minimum number of edges (i.e., length) of such a cycle. If no positive cycle, output 0.

    But careful: The problem statement says "Cycle is such a sequence of rooms a1, a2, ..., ak, that a1 is connected with a2, a2 with a3, ..., ak-1 with ak, ak with a1. Some elements of the sequence can coincide, that is, the cycle should not necessarily be simple. The number of rooms in the cycle is considered as k, the sequence's length. Note that the minimum possible length equals two."

    So cycles can have repeated vertices and edges. They ask: "what minimum number of rooms he will need to visit during one period of a cycle?" That's k, the number of moves? Actually "one period of a cycle" likely means the length of the cycle (number of edges). Since they say "minimum number of rooms he will need to visit during one traverse of the cycle". Usually the number of rooms visited equals the number of vertices in the cycle, but since repeats allowed, maybe they count rooms visited, i.e., the length of the sequence (which is number of edges, because it's a closed walk). They say "minimum number of rooms he will need to visit" might be the number of vertices distinct? But they say "Some elements of the sequence can coincide, that is, the cycle should not necessarily be simple." So if repeats allowed, the length is k, which is the number of moves (edges). And they say minimum possible length equals two. So they count the number of steps (edges) in the cycle. Since a cycle of length 2 would be i->j->i. So indeed they are counting the number of vertices in the walk (including start repeated at end?), they say sequence a1..ak where a1 connected to a2, ..., ak connected to a1. So length k. So we need smallest k such that there exists a directed cycle (closed walk) of length k with total weight > 0. If no positive cycle at all, output 0.

    So this is essentially: In a directed graph with possibly negative edges, find the smallest length (number of edges) of a positive-weight cycle. If positive-weight cycle exists, output its length; else 0. But careful: The total weight must be > 0. And the length is the number of edges in the closed walk. Since cycles can repeat vertices/edges, a positive-weight cycle exists iff there is some cycle (not necessarily simple) with total weight > 0. But if there is any positive-weight cycle, then we can also possibly get a shorter positive-weight cycle? Not necessarily; maybe the smallest positive-weight cycle could be of length 2? For example, an edge from i to j with weight w1 and from j to i with weight w2, then the two-edge cycle i->j->i has total weight w1+w2. So if w1+w2 >0, then answer is 2 if there is no self-loop? But self-loops are not allowed because no door connects a room with itself. So minimum cycle length is 2. But could there be a positive-weight cycle of length 1? That would require a self-loop, which is not allowed. So min length 2.

    So we need to compute the minimal cycle length with positive total weight. This is a classic problem: find the minimum number of edges in a positive-weight cycle. Could be solved using binary search on length? Or using DP with powers of adjacency matrix? Possibly using min-plus matrix multiplication and checking for positive diagonal entries after certain steps.

    Consider we have a directed graph with n nodes, edge weights w(i->j). Define f_k(i, j) = maximum total weight of a walk from i to j using exactly k edges (or maybe we need sum >0). But we want existence of a closed walk of length k with total weight >0. That is, there exists i such that the weight of a walk from i to i of length k > 0. So if we compute the maximum weight over walks of exactly k edges from i to i, we want that >0 for some i. Then answer is smallest k>=2 with that property.

    But there might be positive cycles with length > n? Since cycles can repeat vertices, even if a positive cycle exists, we could possibly find a positive cycle of length <= n? Actually if there is a positive cycle, it may be not simple; but there always exists a simple positive cycle? Not necessarily: Consider a graph where the only positive cycles involve repeating vertices; but if you have a positive cycle that is not simple, you can decompose it into simple cycles (maybe some with positive sum and some with negative). But if the total sum is positive, it's possible that the simple cycles within it have mixed signs. However, if there is any cycle (closed walk) with total weight >0, then there exists a simple cycle with total weight >0? Not always: Example: Two simple cycles: one negative, one positive. The walk goes around the negative cycle many times and then the positive cycle once, net positive. That walk is not simple. But the existence of such a walk implies there is some simple positive cycle? Not necessarily if the positive cycle alone is negative but combination yields positive. Actually if both simple cycles have negative weights, any combination (as integer linear combination) could be positive if the sum of some combination is positive? If both are negative, any nonnegative combination would be negative (since sum of negatives). So at least one simple cycle must be positive. More formally: For directed graphs, if there exists a closed walk with total weight >0, then there exists a simple cycle with total weight >0. This is because any closed walk can be decomposed into a collection of simple cycles (by removing repeated vertices). The total weight is sum of weights of these simple cycles. If all simple cycles have weight <=0, then the sum would be <=0. So by contrapositive, if a closed walk has positive total weight, at least one simple cycle in its decomposition has positive weight. Therefore there exists a simple positive cycle. Thus the minimal length of a positive cycle is at most n (since a simple cycle in a graph with n vertices has length at most n). Actually a simple cycle can have length up to n, but minimal positive cycle length could be less or equal to n. So we can restrict our search to lengths up to n. However, we must consider the possibility that a positive simple cycle could have length n? Possibly. But also note that a positive simple cycle is a directed cycle with no repeated vertices; length between 2 and n. So answer is minimal length among all simple cycles with total weight >0. However, could there be a positive closed walk of length less than any simple positive cycle? For example, suppose there is a simple cycle of length 3 with total weight -1, and another simple cycle of length 5 with total weight +2. The combination of those cycles (walk going around the negative cycle once and the positive cycle once) gives total weight +1, length 8, which is larger than 5. So minimal length positive closed walk might be the positive simple cycle itself if it's length 5. But could we get a positive total weight with length less than the shortest positive simple cycle by combining cycles? For instance, if there is a negative cycle of length 2 with total weight -10, and a positive cycle of length 3 with total weight +6; their combination (one negative + one positive) gives -4, not positive. To get positive, we might need multiple positives to outweigh negative. So length would be at least positive cycle length. Could we get positive by going around a negative cycle a negative number of times? No. So the minimal length positive closed walk is at least the length of the shortest positive simple cycle. Because any closed walk contains at least one simple cycle; if all simple cycles have weight <=0, the total could still be positive if some cycles have positive weight? Actually if there is a simple positive cycle, then that simple cycle itself is a positive closed walk of its own length. So the minimal length positive closed walk cannot exceed the length of that simple positive cycle. However, could there exist a positive closed walk shorter than any simple positive cycle? That would imply that the walk's length is less than the length of every simple positive cycle. But any closed walk of length L must contain at least one simple cycle whose length is at most L (by decomposition). If that simple cycle is positive, then its length <= L, contradiction because we assumed all positive cycles have length > L. If that simple cycle is non-positive (<=0), then the total sum of all cycles (including maybe multiple) could be positive, but the sum of non-positive cycles (negative or zero) plus maybe some positive cycles? But if all simple cycles have weight <=0, then any combination yields <=0. So to have total positive, at least one simple cycle must be positive. Therefore any positive closed walk must contain a positive simple cycle of length <= L. Thus L must be at least the length of that positive simple cycle. So the minimal L is exactly the length of the shortest positive simple cycle. So we need to find the length of the shortest directed cycle (simple) with total weight > 0.

    Thus the problem reduces to: Given a directed graph (possibly with both negative and positive edges), find the shortest cycle (in terms of number of edges) that has total weight positive. If none, output 0.

    Now constraints: n <= 100? Actually input says: "The first line contains two positive integers n and m ( ), where n is the number of rooms, and m is the number of doors in the Smile House." The image is not visible, but from typical problems "Smile House" (maybe from Codeforces). I recall a problem "Smile House" on Codeforces? Let's search memory: I think it's Codeforces Round #... There is a problem "Smile House" maybe from Codeforces 147B? Actually there is Codeforces 147B? I'm not sure. But typical constraints: n up to 300? Actually there is a known problem "Smile House" from Codeforces that uses matrix exponentiation and binary lifting to find minimal positive cycle. I think constraints: n <= 100, m up to n*(n-1)/2? Possibly n up to 300? Let's think: The input says "n and m ()". They likely meant n and m (1 ≤ n ≤ 100, 0 ≤ m ≤ n*(n-1)/2)? But not sure. Since we need to design algorithm, we need to handle n up to maybe 100? Or maybe up to 300? There is a known problem from Codeforces: "147B - Smile House"? I recall a problem "B. Smile House" maybe from Codeforces Round #103? Let's quickly recall: There is Codeforces problem 147B - Smile House? Actually I think it's 1591F? Not sure.

    Better to search memory: There is a problem "Smile House" from Codeforces: I think it's 149E? No.

    Actually I remember a problem: "Smile House" is from Codeforces Round #234 (Div2) maybe? Let me check typical CF problem IDs: There is "B. Smile House" from Codeforces Round #190? I'm going to think about known technique: find smallest cycle with positive sum. This can be solved using binary lifting + min-plus multiplication (or max-plus) to detect if there is a path of length exactly L with total weight > 0 from a vertex to itself. Since n up to maybe 100, we can use DP over lengths up to n, O(n^3) maybe. But if n up to 300, O(n^3) is okay? 300^3 = 27 million, times maybe some factor, might be okay. But there is possibility of n up to 500? Let's read problem statement: it says "The first line contains two positive integers n and m (), where n is the number of rooms, and m is the number of doors in the Smile House." The image is missing; it likely indicates the constraints: maybe 1 ≤ n ≤ 100, 0 ≤ m ≤ n*(n-1)/2? I've seen a similar problem "Smile House" on e-olymp? Possibly constraints: n ≤ 100, m ≤ n*(n-1). Actually typical CF problem: n up to 150? Actually I recall a problem "Smile House" from Codeforces Round #103? Let's think about solution: Usually they use binary search on answer and check using matrix exponentiation with min-plus to see if there exists a positive cycle of length ≤ k. Since k can be up to n maybe, but they want minimal length. Approach: Precompute dp[l][i][j] = max weight path from i to j using exactly l edges. Use doubling to achieve O(n^3 log n). That suggests n maybe up to 150-300. So we can adopt that.

    Given that we need only simple cycles up to n, we could also use Floyd-Warshall with maximum path of exactly length? But we can also use DP: For each length L from 2 to n, check if there is a cycle of length L with total weight > 0. We can compute the maximum weight of a walk of exactly L edges from i to i. However, walks may repeat vertices; but for positive cycles, as argued, the existence of a positive walk of length L implies existence of a simple positive cycle of length <= L. But if we compute maximum weight over all walks (including repeated vertices) of exactly L edges, we might get a positive value even if no simple cycle of length L is positive? Because a longer positive cycle could be combined with zero-weight cycles? But zero-weight cycles maybe don't affect sum? But if there is a positive simple cycle of length L0, then for any L that is a multiple of L0? Actually we can repeat the cycle multiple times to get a walk of length k * L0 with total weight k * (weight of cycle) > 0. So for lengths that are multiples of L0, we get positive. But if we just look for some length L with positive, the minimal such L might be L0, because for L < L0, we cannot get a positive walk if the shortest positive simple cycle length is L0 (as argued). So checking each L from 2 upwards by computing maximum weight over walks of exactly L edges from any i to i would give us the minimal L where that max > 0. This is valid because if there is a positive walk of length L, then there exists a positive simple cycle of length <= L. So the minimal L for which there exists a positive walk equals the minimal length of a positive simple cycle. Because if the minimal positive simple cycle length is L0, then there is a positive walk of length L0 (the simple cycle itself), and for any L < L0, no positive walk exists (otherwise a positive simple cycle of length <= L < L0 would exist). So yes.

    Thus we can compute f[L][i][j] = maximum total weight of a walk from i to j using exactly L edges (allowing repeats). Then check if any f[L][i][i] > 0 for L from 2 to n (maybe up to n). If none, output 0.

    But we need to be careful: Could there be positive walks of length L where L > n? Possibly but we only need up to n because if no positive simple cycle exists, then no positive walk exists at all (since any positive walk contains a positive simple cycle). So we only need to check up to n. However, what about positive walks that are not simple but whose decomposition yields a positive simple cycle of length <= n, so L0 <= n. So minimal L is <= n. So checking up to n is sufficient.

    But careful: The graph may have zero-weight cycles or negative cycles; but they don't produce positive sum. So fine.

    Now we need to compute f[L][i][j] for L up to n. n could be up to maybe 300? O(n^4) would be too high (300^4 = 8.1e9). We need a more efficient method.

    We can use matrix exponentiation style DP: f^L where multiplication is max-plus (or min-plus for maximum? Actually we want maximum weight of exactly L edges). We want to know if any diagonal entry of the L-th power (in max-plus semiring) is > 0. We can compute powers for L up to n using repeated squaring? But we need minimal L. Binary search on L? We can compute matrices for lengths that are powers of two (doubling) and then assemble to check if there is positive cycle up to certain length.

    Better approach: Use binary search on answer (the minimal length). For a given k, we need to check if there exists a positive cycle of length <= k. This can be done by checking if there exists a walk from some i to i with length exactly L <= k and total weight > 0. But we need to consider all lengths up to k. However, we could use the idea of "max-plus matrix exponentiation" to compute the maximum weight for exactly L steps, but to check existence up to k, we might compute the maximum over all lengths <= k. Alternatively, we can compute the maximum weight of any walk with length exactly L, and then we can test for each L individually. But binary search would require O(log n) checks, each check might be O(n^3 log n) or something. Another common solution for this problem is to use doubling to compute the maximal weight for paths of length exactly 2^t, and then use a technique similar to "binary lifting" to find the smallest L such that some diagonal positive appears. I recall a known editorial for "Smile House" uses exactly that.

    Let me think: This is similar to finding the smallest positive cycle in a directed graph with edge weights. They use max-plus multiplication and binary lifting to get O(n^3 log n). Let's attempt to reconstruct.

    Define DP[t][i][j] = maximum weight of a walk from i to j using exactly 2^t edges (or up to 2^t? Typically exactly 2^t). Then we can combine lengths. To check if there is a positive cycle of length <= some bound, we can start from an identity matrix (paths of length 0) and then add powers greedily to build up to the minimal length. Similar to finding the smallest exponent such that matrix power has a positive diagonal in max-plus semiring.

    Specifically, we want the smallest L such that there exists i with (A^L)[i][i] > 0, where A is the adjacency matrix (with weight w(i->j) if edge exists, else -inf). In max-plus semiring, (A^L)[i][j] = maximum total weight over walks from i to j with exactly L edges. We need to find min L>=1? Actually L>=2 because cycles need at least 2 edges. But we can consider L>=1 as well; if there is a self-loop? Not allowed, but if there were, L=1 would be possible. So we consider L>=2.

    We could compute A^L via binary exponentiation. To find minimal L, we can do something like: start from identity matrix B (paths of length 0 with weight 0 on diagonal, -inf elsewhere). We'll try to build length L by adding bits from highest to lowest (like binary lifting). We maintain a current matrix cur that represents the maximum weights for exactly some length (say len) we have so far. Initially len = 0, cur = identity (0 on diagonal, -inf elsewhere). We'll also maintain an auxiliary matrix best that represents the maximum weights for any walk of length exactly len? Actually we want to find the smallest total length such that when we multiply by a certain power, we get a positive diagonal. The method: For t from log2(n) down to 0 (or down to something), we consider if adding 2^t to current length would still not cause any positive diagonal. If not, we add that power (i.e., we update cur = cur * DP[t], and len += 2^t). After processing all bits, we have the maximum length for which there is no positive diagonal? Actually we want minimal L where positive diagonal appears. So we can do: Starting from len=0, cur = identity. We'll try to see if we can reach a state where after adding some power, we get a positive diagonal. At each step, we consider a candidate matrix tmp = cur * DP[t] (where DP[t] stores max weight for exactly 2^t edges). If tmp has no positive diagonal, then it is safe to update cur = tmp and len += 2^t, because we haven't yet reached a length with positive cycle. After processing all bits from high to low, len will be the maximum length such that there is no positive cycle? Actually we want the first length where positive cycle appears. So after the loop, len+1 is the answer? But we need to be careful.

    Standard technique: To find the smallest k such that there exists a path of length exactly k with some property, we can binary lift. For example, in graphs to find the smallest k such that from start to end there is a path of length <=k with max weight >= something. But here we need existence of a positive cycle. We could compute A^L for L from 1 to n but that's O(n^4). But with doubling we can compute A^(2^t) for t up to log2(n) in O(n^3 log n). Then we can binary search on L: For a given L, we can compute A^L using binary exponentiation (multiplication of matrices) in O(n^3 log L). Binary search would cost O(n^3 log^2 n). That might be acceptable for n up to 100-150. But maybe n can be 300? 300^3=27M, times log^2 (like 64) = 1.7B, too high.

    Better is the greedy approach: We want minimal L. We maintain cur as the matrix representing max weights for exactly len edges (starting with len=0 identity). We also maintain an array of precomputed powers P[t] = A^(2^t). Then we iterate bits from high to low. Let's say we want to find the smallest L such that there exists i with (A^L)[i][i] > 0. We can start with L=0? Actually (A^0)[i][i] = 0, others -inf. That's not >0. So positive appears at some L>0.

    We can perform a binary lifting to determine the smallest L. Consider we are at current length cur_len = 0, and we have cur_matrix = identity. We will try to add powers from highest to lowest, but we want to find the first power where adding causes positive diagonal. Usually we do: answer = 0; for t from max_bit down to 0: if (cur_matrix * P[t]) has all diagonal <= 0, then we update cur_matrix = cur_matrix * P[t], answer += 2^t. At the end, answer+1 is the smallest L with positive diagonal? Let's test with simple case: Suppose there is a positive cycle of length 3 only. So A^1, A^2 have no positive diagonal; A^3 has positive. We precompute P[0]=A^1, P[1]=A^2, P[2]=A^4,... max_bit maybe 2 (since n up to maybe 4). We start ans=0, cur=identity. t=2: consider tmp = cur * P[2] = A^4. Does it have positive diagonal? Since there is a positive cycle of length 3, A^4 may also have positive diagonal (by repeating cycle 4? Actually length 4 may also have positive walk: you can do cycle of length 3 + one extra edge? Not necessarily; but if you can add a zero-weight edge? If there is any positive cycle, you can extend it arbitrarily by looping around the positive cycle multiple times, so for any length >= L0, you can get a positive walk (by repeating the positive cycle enough times and then maybe adding some neutral cycles? But you need to have a closed walk of exactly that length. If you have a positive cycle of length L0, then for any length that is a multiple of L0, you can repeat it k times to get positive weight. For lengths that are not multiples, you may still combine with other cycles (maybe zero or negative) to adjust length. However, it's not guaranteed that for all lengths >= L0 there exists a positive closed walk. For example, consider graph with only one positive cycle of length 3 (weight 1). Can we get a positive closed walk of length 4? Possibly if there is some other cycle (even zero weight) of length 1? But no self-loop. Possibly you could do the 3-cycle plus an extra edge that goes somewhere and then back? But that would require a path of length 1 that returns? Actually to have a closed walk of length 4, you could do the 3-cycle and then a 1-cycle? But there is no self-loop. So maybe length 4 might not be possible if the graph has no other cycles of length 1 or 2 that can be appended without destroying positivity? But you could repeat the 3-cycle twice to get length 6, which is positive. For length 4, maybe you could do the 3-cycle and then a 1-step edge that goes to a neighbor and then come back? That would be i->j (some edge) then j->i? That's a 2-cycle. If you have a 2-cycle of weight w, you could do 3-cycle + 2-cycle? That's length 5, not 4. To get length 4, you could do 3-cycle + an extra edge that is part of the cycle? For example, the 3-cycle is a->b->c->a. Could you go a->b->c->a->b? That's not closed. Actually closed walk must start and end at same vertex. So if you do a->b->c->a->b, end at b, not a. So not closed. To keep closed, you need to return to start. So if you have a positive 3-cycle, you could try to traverse it once and then take an extra step that returns to start? That would require an edge from a to somewhere and then back to a in one step? That's a 2-cycle. So length would be 3+2=5. So length 4 might not be achievable. Thus it's possible that A^4 has no positive diagonal. So the condition that there exists positive closed walk for all lengths >= L0 is not necessarily true. So binary lifting method that checks if cur * P[t] has positive diagonal might not be monotonic in the sense that if A^L has positive diagonal, then A^{L+1} might not. So we cannot simply find the first length where positive appears by greedy adding largest powers that keep diagonal non-positive.

    But we are looking for the minimal L such that A^L has positive diagonal. Since A^L may not be monotonic with respect to L, we need to examine each L individually? However, note that if there is a positive cycle of length L0, then for any L >= L0 * n? Not necessarily. Let's think more carefully: If there is a positive simple cycle, we can repeat it multiple times to get lengths that are multiples of L0. But to get arbitrary lengths, we might need to combine with other cycles. But is it guaranteed that for some length <= n there is a positive cycle? Yes, the simple cycle itself is length <= n. So we only need to search up to n. So we could iterate L from 2 to n, compute A^L and check diagonals. The challenge is to compute A^L efficiently for all L up to n.

    We can use DP by dynamic programming over lengths: Let dp[l][i][j] be the maximum weight of a walk from i to j using exactly l edges. We can compute dp[l] from dp[l-1] by dp[l][i][j] = max over k of (dp[l-1][i][k] + w(k->j)). This is essentially matrix multiplication in max-plus semiring. So dp[l] = A^l (with A^1 = adjacency matrix). So we need to compute A^l for l=1..n. This can be done by repeated multiplication: start with A^1; each multiplication O(n^3). So O(n^4) total. If n<=100, n^4=100^4=1e8, maybe borderline but with optimizations could be okay? But typical CF problem might have n up to 300? 300^4 = 8.1e9 too high.

    We need a more efficient approach. Another idea: Since we only need to detect if there exists some L <= n with positive diagonal, we can use the concept of "minimum mean cycle" but that gives average weight, not sum>0. However, we can transform: A cycle with total weight > 0 is equivalent to mean weight > 0. So we are looking for a cycle with positive mean weight. The minimal length among such cycles? There is algorithm to find cycle with maximum mean weight (Karp's algorithm) which gives the maximum mean weight cycle. But we need the minimum length among cycles with positive weight. That is different.

    Karp's algorithm computes max mean weight cycle and also can give the length? It gives the mean weight value, not the length. But we could possibly adapt: The maximum mean weight cycle might be positive; then we know there exists a positive cycle. However, to find the minimum length among positive cycles, we need more.

    Alternative: Use BFS-like DP but with states representing best weight for each node after a certain number of steps, but we need to consider cycles of any length up to n. We could run Floyd-Warshall variant to detect positive cycles? Floyd can detect if there is any positive cycle by checking if after algorithm any diagonal entry > 0? Actually Floyd-Warshall computes all-pairs shortest paths (or longest?) But we can use max-plus to compute the maximum weight path of at most n-1 edges. If after n steps, we can still improve (i.e., A^n has positive diagonal), then there is a positive cycle. But that doesn't give the minimal length.

    We could binary search on the length L and check if there exists a positive cycle of length <= L. To check if there exists a positive cycle of length <= L, we could compute the maximum weight of a walk of exactly l edges for all l up to L? But that's similar to DP. However, we can use a technique with doubling and checking existence of positive cycle up to a certain length using binary lifting combined with a "state" matrix.

    Observing that if there exists a positive cycle of length exactly L0, then for any L >= L0, there might exist a positive cycle? Not guaranteed, as argued. But maybe we can guarantee existence for some L up to n? The simple cycle itself is length <= n. So if we just check up to n, we are safe. But we need efficient computation of A^l for l up to n. There is technique to compute these using exponentiation by squaring with polynomial (min-plus) and binary decomposition of L. Actually to compute A^L for a specific L, we can do binary exponentiation in O(n^3 log L). To compute for all L up to n, we could precompute powers A^(2^t) and then for each L assemble using binary representation. That would be O(n^3 log n) per L if done naively, total O(n^4 log n) even worse. But we can do something else: we want the minimal L such that diag positive. This is like finding the smallest exponent where matrix has a positive diagonal in max-plus semiring. There is a known technique: Use "min-plus" matrix multiplication and binary lifting to find the first time when something becomes possible, by checking if after adding a certain power we can achieve positive diagonal. But this works only if the property is monotonic: if A^L has positive diagonal then A^{L + k} also has positive diagonal for all k? Not true in general, as argued. However, is there a way to transform the problem to achieve monotonicity? Possibly by considering the maximum weight over walks of length at most L? Because if there is a positive cycle of length L0, then for any L >= L0, we can repeat the cycle multiple times to get a positive closed walk of length L * t. But not necessarily for all L. But if we consider the maximum weight over walks of length exactly L, we cannot guarantee monotonicity. But if we consider the maximum weight over walks of length at most L (i.e., best path with up to L edges), then if there is a positive cycle, you can always extend it to any larger length by repeating the cycle, so the maximum weight for at least L would become unbounded? Actually the maximum over up to L might not be monotonic in the sense that the maximum weight over up to L edges could increase with L. But we want existence of a positive closed walk of exact length L? The problem asks for the minimal number of rooms visited (i.e., length of the cycle) that yields positive sum. So it's about exact length.

    But we could approach differently: Since the graph has at most n vertices, any simple cycle length is at most n. So we only need to check lengths up to n. And n might be at most 300? 300^3 = 27 million, times n maybe 300 -> 8.1 billion. Too high.

    We need better: O(n^3 log n) perhaps. Let's try to think of known solutions to this problem. Searching memory: I recall a Codeforces problem "Smile House" (maybe 147B) that indeed uses binary lifting + matrix multiplication. The editorial: They precompute matrices for powers of two, then use a technique similar to finding the smallest k such that there exists a positive cycle. They treat the problem of finding minimal length of a positive cycle. The solution does:

    • Let f[t][i][j] be the maximum weight of a walk from i to j with exactly 2^t edges.
    • Then they start with a base matrix cur which is the identity (paths of length 0). Also maintain an auxiliary matrix tmp. Then they iterate bits from high to low. They maintain a candidate length ans initially 0. For each bit, they compute nxt = cur * f[bit]. If nxt has no positive diagonal, then they set cur = nxt and ans += 2^bit. After processing all bits, they check if cur * f[0] has a positive diagonal? Actually they then output ans+1 or maybe ans? Let's derive.

    They likely rely on the fact that if there is a positive cycle, then there exists some L such that A^L has positive diagonal. However, as we argued, monotonicity does not hold, but maybe the approach works because they are not checking exact lengths but they are building the length greedily while ensuring that no positive cycle exists for lengths less than current candidate. Actually they might be searching for the smallest L such that there exists a positive cycle of length <= L? Or they might be using the concept of "if there is a positive cycle, then for some length up to n, A^L has positive diagonal; moreover, if we consider the property 'exists positive cycle of length at most L', that property is monotonic: if there is a positive cycle of length <= L, then for any larger L' >= L, there is also a positive cycle of length <= L'? Not exactly: if there is a positive cycle of length L0 <= L, then it's also <= L' for L' >= L0. So the set of L for which there exists a positive cycle of length at most L is upward closed from the minimal L0. That is monotonic: exists_positive_up_to(L) is false for L < L0 and true for L >= L0. So that property is monotonic! Because if there exists a positive cycle of length at most L, then for any L' >= L, there exists a positive cycle of length at most L' (the same cycle). So the predicate P(L) = "there exists a positive cycle with length <= L" is monotone non-decreasing in L. Indeed, if a positive cycle exists with length L0, then for all L >= L0, P(L) is true; for L < L0, false. So we can binary search on L to find the smallest L such that P(L) is true. That is valid.

    Now we need to check P(L): does there exist a positive cycle of length at most L? Equivalent to: Is there some l in [2, L] such that A^l has a positive diagonal? But we need to check existence up to L efficiently.

    We can compute the maximum weight over walks of length exactly l, but we need up to L. However, we could compute the maximum weight over walks of length at most L? Not exactly, because a positive cycle of length <= L may have weight > 0, but there could be longer walks with positive weight that have length <= L? Actually the cycle itself is a walk of exactly its length. So we need to check if any A^l for l<=L has positive diagonal. That's a range query.

    We could compute the matrix for all lengths up to L using DP, but that's O(L n^3). However, we can use binary lifting to compute something like "is there a positive cycle of length at most 2^k?" Possibly we can combine precomputed matrices to check up to a certain length.

    Idea: We can compute, for each t, the maximum weight of a walk from i to j using exactly 2^t edges. Then to check if there is any positive cycle of length <= L, we can try to see if there exists a decomposition of some l <= L such that the product (in max-plus) of some matrices yields a positive diagonal. But that's not straightforward because we need existence for any l, not necessarily a combination of powers that sum to exactly L.

    But we can use the following: Since we want to know if there is a positive cycle of length at most L, we can compute the matrix of maximum weights for paths of length at most L? However, computing that directly might be as hard.

    Alternatively, we could binary search on L and for each mid, compute the maximum weight of a walk of length exactly mid, but that would be O(n^3 log mid) per check, and binary search adds another log factor, total O(n^3 log^2 n). For n up to 300, n^3 = 27e6, log^2 ~ 100, so 2.7e9, too high. But maybe we can reduce constant or use faster multiplication (e.g., using bitset). However, typical CF constraints maybe n ≤ 150, then n^3=3.375e6, times 150? No, log n ~ 8, log^2 ~ 64, gives about 216 million, which might be okay in C++ with optimization? Possibly.

    But maybe there is a more clever approach: The answer is at most n (if any positive cycle). So we can just iterate L from 1 to n and compute A^L using exponentiation by squaring on the fly? Actually we can iteratively multiply: start with current = identity (length 0). For len from 1 to n: current = current * A (in max-plus). This is O(n^4) if we do naive multiplication each step (O(n^3) per multiplication). That's O(n^4). But we can do faster? Actually each multiplication is O(n^3). Doing it n times gives O(n^4). For n=300, that's 8e9, too high.

    But we can use matrix exponentiation by squaring to compute each power quickly? Not really because we need all powers sequentially; we could use repeated squaring to compute A^2, A^4, A^8, etc., but to get A^3 we need combination, which again requires multiplication. So iterating L from 1 to n seems heavy.

    Wait, maybe n is small. Let's search memory: I think the problem "Smile House" originally had n up to 100. Actually I'm trying to recall from Codeforces: I think there is a problem "147B - Smile House" with n ≤ 100, m ≤ n*(n-1)/2? Let me check quickly: I remember a problem "B. Smile House" from Codeforces Round #234 (Div2)? Actually I'll search my mental database: I recall seeing a problem "Smile House" on CF with constraints n ≤ 100, m ≤ n*(n-1). The solution used Floyd-Warshall with bitset? Not sure.

    Let's try to locate: There is a known problem "Smile House" from Codeforces Round #203 (Div1) maybe? Let's think: There is a problem "367C" no.

    Better approach: Let's check online memory: I think it's Codeforces 147B - Smile House? Actually 147 is a round, I recall problem "B. Smile House" might be from round #112? Hmm.

    If I were to guess, typical constraints for such problem: n ≤ 100, m ≤ n*(n-1). Because O(n^3 log n) is comfortable. Actually many solutions for this problem indeed use binary lifting: they compute matrices for 2^k steps, then they try to construct the longest prefix without positive cycle, answer = that prefix length + 1. That is the greedy approach I described earlier. And they claim it works. Let's examine that greedy approach more carefully.

    The greedy approach: Precompute f[t][i][j] = max weight path from i to j using exactly 2^t edges (or maybe up to 2^t? Usually exactly). Then set cur[i][j] = -inf, and set cur[i][i] = 0 (paths of length 0). Also set ans = 0. Then for t from max_bit down to 0: compute tmp[i][j] = max over k (cur[i][k] + f[t][k][j]). If for all i, tmp[i][i] <= 0 (no positive diagonal), then set cur = tmp and ans += 2^t. After loop, if we can add one more edge (i.e., after the loop, there exists a walk of length ans+1 with positive diagonal?), then answer = ans+1, else 0. The intuition: We are building the longest length for which we can guarantee that there is no positive cycle of that length? Actually we are trying to find the largest L such that there is no positive cycle of length <= L. Then answer = L+1. Since the property "no positive cycle of length <= L" is monotone (if there is no positive cycle of length <= L, then for all smaller lengths also none). So the set of L where property holds is prefix from 0 up to some max L_max. So we can binary search or use greedy addition of powers of two to determine L_max. The greedy addition of powers works because we are checking if adding 2^t to the current length would still result in no positive cycle of length <= current+2^t. How to check that? The condition we test: after adding the 2^t edges (i.e., considering walks of length cur_len + 2^t), does there exist a positive diagonal? That is, if we have cur representing max weights for walks of exactly cur_len (or maybe the maximum over all walks of length exactly cur_len), and we multiply by f[t] (max weights for exactly 2^t edges), we get max weights for walks of length cur_len+2^t. If that matrix has no positive diagonal, then there is no positive cycle of length exactly cur_len+2^t. But we need to ensure there is no positive cycle of any length <= cur_len+2^t. However, if we have already ensured that for all lengths <= cur_len there is no positive cycle (by inductive assumption), then checking that after adding 2^t there is no positive cycle of exactly cur_len+2^t ensures that for all lengths up to cur_len+2^t there is none. But is that sufficient? What about lengths between cur_len+1 and cur_len+2^t -1? Those could potentially have positive cycles even if exact cur_len+2^t does not. But we are adding powers from high to low; we will eventually cover all lengths in binary representation. The algorithm builds cur_len as sum of selected powers, and after processing all bits, cur_len will be the maximum length for which we have verified no positive cycle? The standard technique: To find the smallest L such that a property holds (where property is monotone increasing), we can binary search. However, the greedy addition of powers is akin to constructing the largest L for which property is false, by checking at each bit whether we can extend by that power while keeping property false. This works only if we can efficiently test the property for candidate lengths that are sums of selected powers. But here the property we test at each step is: "there is no positive cycle of length <= current + 2^t". If we can test that efficiently using the precomputed matrices, then we can decide whether to add 2^t or not.

    But is "no positive cycle of length <= L" equivalent to "the max over i of (some matrix representing best walks of length exactly L) <= 0"? Not exactly, because there might be positive cycles of length less than L but not of length exactly L. However, if we have already ensured that there is no positive cycle for all lengths up to cur_len (by previous steps), then to extend to cur_len+2^t, we need to ensure that there is no positive cycle for lengths in (cur_len, cur_len+2^t]. But we only check length exactly cur_len+2^t. To guarantee that no positive cycle exists for lengths in that interval, we need more.

    Maybe the algorithm actually uses the concept of "max weight over walks of length exactly L" and checks positive diagonal. Since property "exists positive cycle of length exactly L" is not monotone, but "exists positive cycle of length <= L" is monotone. However, the algorithm's test of checking exact length after adding a power may not be sufficient unless we maintain more information.

    Let's think about typical solution for "minimum cycle length with positive weight" in directed graphs. I recall a known approach: Use binary lifting on the "max-plus" adjacency matrix to find the smallest L such that there is a positive cycle. The algorithm works because if there is a positive cycle, then there is a positive cycle whose length is at most n. And they use the fact that if there is a positive cycle of length <= L, then there is a positive cycle of length exactly some power-of-two combination? Not exactly.

    Alternatively, they could be using the idea that we are looking for the smallest L such that the L-th power of the adjacency matrix (in max-plus semiring) has a positive diagonal. And they find L by binary search on L using fast exponentiation: for each mid, compute A^mid and check diagonal. That's O(n^3 log n * log n) as earlier.

    Given that n might be up to 300, O(n^3 log^2 n) could be about 27e6 * (8*8) ≈ 1.7e9, too high. But maybe they use O(n^3 log n) by a more clever method: They precompute powers A^(2^t) and then for binary search they compute A^mid by multiplying appropriate powers, which takes O(n^3 log mid). With binary search, total O(n^3 log^2 n). However, if n is 100, 1e6 * 64 = 64e6, okay.

    I suspect n is at most 100 because the problem is from an old contest and typical constraints for matrix multiplication problems were n <= 100. Let's check memory: There is a Codeforces problem "147B - Smile House"? Actually I'm going to google mentally: I recall a problem "Smile House" on Codeforces with ID 147B? Not sure. Wait, I think there is problem "147B" is "Smile House"? I might be confusing with "147B" which is "Lucky Tree"? No.

    Let me search my mind: I've seen an editorial: "Solution: Use binary lifting on the matrix of max-plus multiplication to find the smallest k such that there is a positive cycle." That suggests n up to 150 maybe. So O(n^3 log n) is typical.

    But the greedy addition method would be O(n^3 log n) without binary search, which is even better. Let's try to understand if that method indeed works.

    We want to find the smallest L such that there exists a positive cycle. Define F(L) = true if there exists a positive cycle of length <= L. F is monotonic. The greedy method can compute the maximal L for which F(L) is false by checking in order from high bits to low bits whether we can extend the current length by 2^t while keeping F(current+2^t) false. To check F(current+2^t), we need to know if there exists a positive cycle of length <= current+2^t. Since we have already ensured that there is no positive cycle of length <= current, we only need to check lengths from current+1 to current+2^t. That's a range. Can we check that using precomputed matrices? Possibly we can compute the best weights for walks of exactly length current+2^t, but that only checks one length, not the range.

    However, maybe we can maintain not just the matrix for exact length current, but also the matrix for the best weights for any length up to current (i.e., the maximum over all lengths <= current). That would be more useful. If we maintain a matrix cur that gives the maximum weight over all walks of length at most cur_len (or exactly? Hmm). Then when we consider adding 2^t, we could compute new matrix = cur * P[t] (or something) that would give maximum over walks of length up to cur_len+2^t? But multiplication in max-plus corresponds to concatenating walks: If cur holds max over lengths up to cur_len, and P[t] holds max over exactly 2^t, then cur * P[t] yields max over walks that first take up to cur_len edges, then exactly 2^t edges, resulting in total length in [2^t, cur_len+2^t]? Actually if cur is max over lengths up to cur_len, then for any i,j, cur[i][k] is the max weight over any walk from i to k with length between 0 and cur_len (with length 0 only for i=j, weight 0). Then for each k,j, we add weight of a walk from k to j of exactly 2^t edges. The concatenated walk length is between 2^t and cur_len+2^t. So the resulting matrix gives the max weight over walks with length in that interval. However, we also need to consider walks that are purely from cur (i.e., lengths <= cur_len). But we already know those have no positive cycle (since we've ensured that). So to check if there is any positive cycle of length <= cur_len+2^t, we need to check if there is any cycle in that combined set (including previously checked lengths and new lengths). Since we already know no positive cycle for lengths <= cur_len, we only need to check the new lengths (cur_len+1 to cur_len+2^t). But the combined matrix from cur * P[t] yields walks of lengths up to cur_len+2^t, but it also includes walks of length < cur_len+1? Actually minimal length from cur * P[t] is at least 2^t (if we take length 0 from cur? But cur includes length 0 only for i=j, with weight 0. So when i=j, cur[i][i] = 0 (length 0). Then cur[i][i] + P[t][i][i] could correspond to a walk of length exactly 2^t (starting at i, take 0 steps, then a walk of length 2^t from i to i). That yields length exactly 2^t. So the concatenation covers lengths from 2^t up to cur_len+2^t. But we need to cover all lengths from 1 to cur_len+2^t. The lengths from 1 to cur_len are already covered by previous cur (but we've checked they are safe). So to check the whole range up to cur_len+2^t, we need to ensure that neither the existing walks (cur) nor the new concatenated walks have a positive cycle. However, we already know cur has no positive diagonal (since for all i, the maximum over walks of length <= cur_len is <= 0? But careful: cur stores the maximum weight over walks of length exactly cur_len? In typical algorithm, they store matrix for exact length, not up to. But maybe they store "best for exact length" and rely on the fact that if there is a positive cycle of length L, then for some power-of-two decomposition, the concatenation of exact-length matrices will also produce a positive diagonal for a length that is a sum of powers of two? Not necessarily, because L may not be representable as sum of powers of two that we have selected? But any integer can be represented as sum of powers of two. So if we have matrices for exact lengths 2^t, we can represent any length L as sum of such powers. Then we can compute the matrix for exactly L by multiplying the corresponding powers. So we can test exact L by multiplication of selected powers. So if we want to test whether there exists any L <= current+2^t that yields a positive diagonal, we would need to test all L in that range, which is many. However, the greedy method checks only one exact length: current+2^t. So it cannot guarantee that no smaller length in that range is positive.

    Wait, but maybe the algorithm is designed to find the smallest L such that there exists a positive cycle, not using monotonicity of "exists positive cycle of length exactly L", but using the following insight: In max-plus algebra, if there is a positive cycle of length L, then for any k >= L, there exists a walk of length k with positive weight? Is that true? Let's test with earlier counterexample: positive cycle length 3 weight 1, other edges maybe nonexistent or negative. Can we get a positive walk of length 4? Suppose graph: vertices 1,2,3 with edges: 1->2 weight 0? Actually need to construct a graph where only positive cycle is 3-cycle, and there is no way to get a positive closed walk of length 4. Is that possible? Consider graph: vertices A,B,C. Edges: A->B weight 0, B->C weight 0, C->A weight 1 (positive). That's a 3-cycle with total weight 1. Are there any other edges? Only those three? Then any closed walk must have length multiple of 3? Because the graph is a directed cycle of length 3. Any walk that starts and ends at same vertex must have length divisible by 3. Because each step moves along the cycle. Actually you could also have walks that go around multiple times. So length 4 is impossible because 4 mod 3 = 1, you cannot return to start after 4 steps? Starting at A: A->B (1), B->C (2), C->A (3), A->B (4) ends at B, not A. So there is no closed walk of length 4 at all, let alone positive. So indeed, A^4 has -inf on diagonal (or very negative). So existence of positive cycle does not guarantee positive diagonal for all larger lengths. So property "A^L has positive diagonal" is not monotonic.

    Thus binary search on L using existence of positive diagonal for exact L does not directly give answer for minimal L because maybe the minimal L is 3, but L=4 yields false, L=5 maybe false, L=6 true, etc. But the predicate "exists positive cycle of length <= L" is monotonic, but we cannot test it by just checking A^L; we need to check all lengths up to L. However, we can compute the maximum over all lengths up to L using a technique: we can compute the matrix of best weights for walks of length at most L by