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

Friends Alex and Bob live in Bertown. In this town there are n crossroads, some of them…

  1. User

    Friends Alex and Bob live in Bertown. In this town there are n crossroads, some of them are connected by bidirectional roads of equal length. Bob lives in a house at the crossroads number 1, Alex — in a house at the crossroads number n.

    One day Alex and Bob had a big quarrel, and they refused to see each other. It occurred that today Bob needs to get from his house to the crossroads n and Alex needs to get from his house to the crossroads 1. And they don't want to meet at any of the crossroads, but they can meet in the middle of the street, when passing it in opposite directions. Alex and Bob asked you, as their mutual friend, to help them with this difficult task.

    Find for Alex and Bob such routes with equal number of streets that the guys can follow these routes and never appear at the same crossroads at the same time. They are allowed to meet in the middle of the street when moving toward each other (see Sample 1). Among all possible routes, select such that the number of streets in it is the least possible. Until both guys reach their destinations, none of them can stay without moving.

    The guys are moving simultaneously with equal speeds, i.e. it is possible that when one of them reaches some of the crossroads, the other one leaves it. For example, Alex can move from crossroad 1 to crossroad 2, while Bob moves from crossroad 2 to crossroad 3.

    If the required routes don't exist, your program should output -1. Input

    The first line contains two integers n and m (2 ≤ n ≤ 500, 1 ≤ m ≤ 10000) — the amount of crossroads and the amount of roads. Each of the following m lines contains two integers — the numbers of crossroads connected by the road. It is guaranteed that no road connects a crossroads with itself and no two crossroads are connected by more than one road.

    Output

    If the required routes don't exist, output -1. Otherwise, the first line should contain integer k — the length of shortest routes (the length of the route is the amount of roads in it). The next line should contain k + 1 integers — Bob's route, i.e. the numbers of k + 1 crossroads passed by Bob. The last line should contain Alex's route in the same format. If there are several optimal solutions, output any of them.

    Examples

    Input

    2 1 1 2

    Output

    1 1 2 2 1

    Input

    7 5 1 2 2 7 7 6 2 3 3 4

    Output

    -1

    Input

    7 6 1 2 2 7 7 6 2 3 3 4 1 5

    Output

    6 1 2 3 4 3 2 7 7 6 7 2 1 5 1

  2. DeepSeek Assistant

    We need to solve problem: Bob from 1 to n, Alex from n to 1. They must move simultaneously step by step, each step moving along one road (they cannot stay). They both must take exactly k steps (the route length). So they both must have a path of length k from start to destination, and they must not be at the same crossroad at the same time step. They are allowed to meet on a road if they pass each other in opposite directions (i.e., if at time t they are at different ends of an edge and at time t+1 they swap positions, then at the intermediate moment they cross in the middle - that's allowed). Meeting at crossroads (i.e., occupying the same node at the same integer time) is not allowed.

    We need to find the minimum possible k such that there exist two paths: Bob: v0=1, v1, v2, ..., vk=n; Alex: u0=n, u1, u2, ..., uk=1, with (v_i, v_{i+1}) and (u_i, u_{i+1}) are edges, and for all i (time step indices, i from 0 to k), we require v_i != u_i. Also they must move simultaneously and steps are synchronized. Additionally, they must have the same number of streets (k), and it's the minimum such k. Output k and both sequences.

    Observation: This is essentially a problem of two walkers moving synchronously on an undirected graph, with constraints that they avoid collisions at nodes. They can cross on edges. We need paths of equal length from start to end.

    We can think of it as finding a path for Bob and a path for Alex that are of same length and node-disjoint at same times, but they can share nodes at different times (e.g., Bob visits node at time i, Alex visits same node at time j, j != i, is allowed). They can also use same edges possibly at same time (if they cross) which would correspond to v_i = u_{i+1} and v_{i+1} = u_i. That's allowed.

    This is reminiscent of a problem that can be modeled by constructing a graph of pairs of positions (state (a,b) where a is Bob's node, b is Alex's node) and transitions: both move simultaneously along edges: from (a,b) to (a',b') where (a,a') and (b,b') are edges. We need to go from (1,n) to (n,1) without ever having a == b (forbidden). And we need the shortest number of steps (k) to reach (n,1) under these constraints. Since both move each step, the length of each path equals the number of steps. So minimizing steps is equivalent to finding the shortest path from (1,n) to (n,1) in this state graph where states with a=b are forbidden, and transitions are allowed only if they are not staying (they must move each step). The state graph size is O(n^2) with up to 500 nodes -> 250,000 states. Each state can have up to degree (deg(a) * deg(b)) transitions, which could be large (up to maybe (max degree) about n, but with m up to 10k, average degree ~40, so product could be up to ~1600 per state, which could be up to 400M total if all combinations are considered. But we can handle it by BFS and enumerating neighbors on the fly. Since n=500, n^2=250k, and each state can have up to deg(a)deg(b) transitions. In worst case, if graph is dense, m is only 10000, so max degree is at most n-1=499, but m=10000 limits sum of degrees = 2m =20000, so average degree is 40, but maximum could be up to n-1=499 if many edges. But if there is a node with degree 499, then the sum of degrees is at least 499, but m=10000 means sum of degrees=20000, so could have multiple high-degree nodes. For example, if graph is complete, m = n(n-1)/2, for n=500, m = 124750, which exceeds limit, so not possible. So maximum degree is limited by m. The worst-case degree could be around maybe 500? Let's approximate: The maximum sum of degrees is 20000, so average degree 40. The maximum degree could be up to 20000 if all edges incident to one node, but that would be 10000 edges, each connecting that node to others, so degree up to 10000? But n=500, so maximum degree is n-1=499. So it is bounded by 499. So maximum product could be up to 499*499 ~ 250k per state, but such state would be where both a and b have degree 499, but if both have degree 499, then the graph would be almost complete, requiring many edges. Since total edges is only 10000, having many high-degree nodes would exceed the limit. Let's think: The total sum of degrees is 20000, so if one node has degree 499, that's okay. Two nodes each degree 499 would sum to 998, leaving 19002 for others, but each other node max degree 499. But to have many nodes with high degree, the total edges increases rapidly. The maximum possible average degree given n=500 and m=10000 is 40. So the average product deg(a)deg(b) across all pairs could be approximated by (average degree)^2 = 1600, but many states will have smaller product. So BFS on state graph with 250k states and exploring each neighbor might be feasible, as total transitions explored would be sum_{states} deg(a)deg(b). This sum equals sum_{a,b} deg(a)deg(b) = (sum_a deg(a))(sum_b deg(b)) = (2m)(2m) = 4m^2 = 400 million if we consider all ordered pairs (a,b). But note that we only BFS from (1,n) and visit reachable states; not all states are reachable. However, worst-case could be close to all states. With m up to 10000, 4m^2 = 400 million, which might be high but possibly still manageable with careful implementation in C++? Python might be borderline but maybe okay with optimizations? But we need to write solution presumably in C++? The problem is from Codeforces? Usually such constraints (n<=500, m<=10000) are designed for O(n^3) or O(nm) solutions. There is known technique: treat as BFS on state space with pruning.

    Alternative approach: Since we only need equal-length paths, we can think of them as two walks that avoid collisions. The state (a,b) is natural. The BFS will find minimal steps.

    We also need to output the actual paths. So we need to store parent pointers for the BFS state. For each state (a,b) we need to know from which previous state (a_prev, b_prev) we came, and also which moves (edges). That's doable.

    But careful: The BFS will treat each step as both moving simultaneously. The transition: from (a,b) to (a',b') if (a,a') and (b,b') are edges, and a' != b' (since after the move they cannot be at same crossroad). Additionally, we must also forbid that before the move they are at same node? The condition only says they cannot appear at the same crossroads at the same time. That includes the start time (t=0). So initial state (1,n) must have 1 != n, which is true. At each step after moving, we require that v_i != u_i for all i. So the condition for state (a',b') is a' != b'. However, what about during the movement? They can meet in the middle of street when moving opposite directions. That scenario occurs when a = b' and a' = b. In terms of state transition, this corresponds to (a,b) -> (b,a) where (a,b) is an edge? Actually if they cross, then at time t they are at a and b, at time t+1 they are at b and a. This is allowed even though a and b might be equal? But a and b are distinct initially? In crossing scenario, they are at opposite ends of same edge. So at time t: Bob at u, Alex at v, with edge (u,v). At time t+1: Bob at v, Alex at u. That's allowed. In state representation, we transition from (a,b) to (b,a). But we must check the condition: After move, we require a' != b'. But here a' = b, b' = a, so a' != b' is true as long as a != b. Also during the move, they meet in the middle; that's allowed. So crossing is allowed. So the BFS transition doesn't need any extra condition.

    Additionally, what about them moving along the same edge in the same direction? That would mean they are one behind the other? That is allowed as long as they don't occupy same node at same time. For instance, if Bob is at node x, Alex at node y, and they both move to node z along edges (x,z) and (y,z). At time t+1 they would both be at z, which is forbidden because a'=z, b'=z => a'=b'. So that move is forbidden. So the condition a' != b' automatically prevents that.

    Also what about them moving such that they swap via an intermediate node? That's fine.

    So BFS on (a,b) with forbidden a==b is correct.

    Goal: (n,1). Minimal steps.

    Now constraints: n<=500, m<=10000. State space 250k. BFS with adjacency enumeration can be done.

    But need to ensure BFS complexity is okay. Let's estimate worst-case edges: For each state (a,b), we need to iterate over neighbors of a and neighbors of b. So time per state = deg(a)*deg(b). In worst-case if graph is dense but m limited, deg(a)*deg(b) max might be like (max_deg)^2, but average over all states might be large. However, BFS may not visit all states, but can in worst case? Let's think of a complete graph with n=500 but m would be too big. Actually m=10000 corresponds to average degree 40, not full. Let's approximate worst-case total BFS transitions visited: For each visited state (a,b), we enumerate all pairs of neighbors. The sum over visited states of deg(a)*deg(b). If BFS visits many states, say all 250k, and the degrees vary, we can approximate worst-case sum as something like: sum_{a,b} deg(a)*deg(b) = (sum deg)^2 = (2m)^2 = 4m^2 = 400 million. That's a lot but maybe doable in C++ if we use efficient loops? 400 million operations might be near the limit but possibly okay within 2 seconds? Usually 4e8 operations is heavy. But we can optimize.

    We can also think of BFS from both sides? Or we can use alternative modeling: Since the movement is symmetric, we might think in terms of "time steps" and use BFS on Bob's path while ensuring Alex's path can avoid collisions. But the problem is about both moving simultaneously; might be solved with a flow or matching? But BFS on pairs is the most straightforward.

    We can perhaps reduce complexity by noticing that the graph is undirected and the state transition can be considered as moving in a product graph. But we can also precompute adjacency lists for each node, and during BFS we can for each state (a,b) iterate through neighbors of a, and for each neighbor a', we iterate through neighbors of b. That's the product.

    We can also consider using BFS with queue and visited array of size nn. Since n=500, nn = 250000, visited as bool array is fine.

    Potential improvements: If we BFS from (1,n) to (n,1), we can early stop.

    Now, we also need to output paths. To reconstruct, we store for each state (a,b) its parent state (prev_a, prev_b). Also maybe store the move (the edges used) but we can derive from parent. Since we know from (prev_a, prev_b) to (a,b), we know Bob moved from prev_a to a, Alex moved from prev_b to b. So we can reconstruct sequences by backtracking from (n,1) to (1,n). We need to output k+1 crossroads for each. That is fine.

    One nuance: The paths must have exactly k steps. BFS will give us minimal k. So the path length (number of edges) for each is exactly k.

    Now, check sample:

    Sample 1: n=2, m=1 edge (1,2). Initial (1,2), goal (2,1). Check transitions: From (1,2), neighbors: a' can be 2 (since neighbor of 1), b' can be 1 (neighbor of 2). So (2,1) is reachable in 1 step. And condition a'!=b' holds? 2!=1 yes. So k=1, paths: Bob: 1 2, Alex: 2 1. Works.

    Sample 2: Output -1. We'll test later.

    Sample 3: Output given.

    Now need to confirm that BFS will find minimal k and guarantee that they never meet at crossroads at same time. The BFS prohibits states with a==b, so that ensures they are never on same node at same integer time. Also the start state is fine. But what about meeting at the same time at the same node not exactly at integer times but at some intermediate moment? The problem only disallows meeting at crossroads (nodes) at the same time (presumably at same moment), but allows meeting in the middle of street. So we don't need to worry about times between steps; they are moving continuously at equal speeds along edges. The only potential collision is if they both go to same node at same step (they arrive at the same time), which is disallowed. If one arrives at a node at time t and the other leaves that node at time t, is that allowed? The problem statement: "It is possible that when one of them reaches some of the crossroads, the other one leaves it." That is allowed. So at time t, if Bob arrives at node v and Alex leaves node v at the same moment, they are both at the node at the same time? Actually if they are exactly at the node at the same instant, that would be meeting. But the statement says it's possible that when one reaches, the other leaves it. Typically in discrete time model, if Bob moves from u to v and Alex moves from v to w, then at time t Bob is at u, Alex at v; at time t+1 Bob is at v, Alex at w. So at integer times, they are not both at v simultaneously because at time t+1 Bob is at v and Alex is at w. So they don't occupy same node at integer times. However, at the exact moment when Bob arrives at v, Alex departs from v, but that moment is continuous. The problem likely considers that as allowed, because they said "Alex can move from crossroad 1 to crossroad 2, while Bob moves from crossroad 2 to crossroad 3." That implies that if Alex is at crossroad 2 at time t, and Bob moves from 2 to 3 at same step, then at time t Alex is at 2, Bob is at 2? Wait careful: In the example they gave: "Alex can move from crossroad 1 to crossroad 2, while Bob moves from crossroad 2 to crossroad 3." In that scenario, at time t (start of step), Alex at 1, Bob at 2. Then they both move along edges. After moving, at time t+1, Alex at 2, Bob at 3. So at time t, Alex not at 2; Bob at 2. At time t+1, Alex at 2, Bob at 3. So they never simultaneously are at 2. So it's fine. The statement "when one of them reaches some of the crossroads, the other one leaves it" could be interpreted as the scenario where they are at the same node at the same time? Actually no: If at time t Alex is at node X and leaves it to Y, and at time t Bob arrives at X from Z, then at the start of the step (time t) Alex is at X, Bob is at Z; at the end of step (t+1) Alex at Y, Bob at X. So they are never at X at same integer time. So the condition that a_i != u_i at all i ensures they never coincide at integer times. But there could be a scenario where they meet exactly at a node at a non-integer time if they arrive at exactly the same moment? For two walkers moving at constant speed along edges, if they start at same time and move, they could meet at an intermediate point on an edge (allowed), or at a node if they both arrive at the node at the same instant. That could happen if one travels from u to v, the other from w to v, and they arrive at v at the same time. In our discrete model, if they both move to v in the same step, then at time t+1 they would both be at v, which is forbidden because state (v,v) is disallowed. So we disallow that. Also if one arrives at v at time t+1 and the other leaves v at time t+1? But leaving at time t+1 means they start moving from v to somewhere at time t+1? Actually movement occurs in steps: at each integer time they are at nodes; between t and t+1 they travel along edges. So if at time t, one is at v and leaves v to somewhere, at time t+1 they are at the other node. If at time t, the other is at some node u and moves to v, at time t+1 they arrive at v. So both are at v at time t+1? No, the one who left v is no longer at v at time t+1. So they are not simultaneously at v at integer times. The only way they could be at v at the same continuous moment is if they both are at v at the same instant, which would correspond to either both being there at integer times or one arriving exactly when the other is there at the start of the step. But at the start of step (integer time), if Alex is at v and Bob is at v, that's forbidden. If Alex is at v at time t, and Bob is moving from u to v, then at time t Alex is at v and Bob is somewhere on edge, not at v. At time t+1 Bob arrives at v, but Alex has left to w if he moved. If Alex stayed at v, he would be there at time t+1 as well, but they cannot stay; they must move each step. So Alex must leave v at time t. So Alex cannot be stationary. So there is no scenario where they are both at v at the same continuous moment without being there at same integer time. Because at any time between t and t+1, Bob is on edge, Alex is on edge. They could meet at midpoint of edge if crossing. But that's allowed. So the condition a_i != u_i suffices.

    Thus BFS on product graph with forbidden same-node states works.

    Now complexity: BFS from (1,n). We'll need adjacency list for each node. Precompute.

    Implementation details:

    • Input n, m.
    • Build adjacency lists for nodes 1..n.
    • BFS queue (maybe using deque). Distances array dist[n+1][n+1] initialized to -1 (or INF). Also parent array: prev[n+1][n+1] as pair (prev_a, prev_b) or maybe separate arrays.
    • Start state: (1,n). Set dist[1][n]=0. parent[1][n]=(-1,-1).
    • While queue not empty:
      • pop (a,b). If (a,b) == (n,1), break.
      • For each neighbor a' of a: For each neighbor b' of b: if a' != b' and dist[a'][b'] == -1: dist[a'][b'] = dist[a][b] + 1 parent[a'][b'] = (a,b) push (a',b')
    • After BFS, if dist[n][1] == -1, output -1.
    • Else: k = dist[n][1] Reconstruct path: Bob's path of length k+1 nodes; Alex's path of length k+1 nodes. We'll backtrack from (n,1) to (1,n). We'll collect the sequence of states (a,b). For each step, we have current (a,b). Store Bob's node a and Alex's node b at each time from final to start. Starting from (n,1) at time k, we go back to parent (a_prev,b_prev) which corresponds to time k-1. So we can store arrays bob_path[k+1], alex_path[k+1]. For i from k down to 0: set bob_path[i] = a, alex_path[i] = b; then move to parent. Finally we have sequences from time 0 to k. Then output k, bob_path, alex_path.

    Edge Cases:

    • What if n=1? But n≥2.
    • What about loops? No self-loops.
    • Ensure that we treat node indices as 1..n.

    Now confirm sample 2: n=7, m=5 edges: 1-2, 2-7, 7-6, 2-3, 3-4. BFS would likely find no path to (7,1) because to get to 7 for Bob, and 1 for Alex. Bob must go from 1 to 7, only path is 1-2-7 (length 2). Alex from 7 to 1: 7-2-1 (length 2). So both minimal path lengths are 2. But they would meet at crossroad 2 at time 1? Let's simulate: Bob: 1->2->7, Alex:7->2->1. At time0: (1,7). Time1: Bob moves to 2, Alex moves to 2? Actually from 7 Alex's neighbor to 1 is 2? Edge 7-2 exists, yes. So Alex moves from 7 to 2. So at time1 both at 2 -> collision forbidden. Could they take longer routes to avoid? Need equal length. Let's see if they can take k=3 routes? Bob must start 1 and end 7. Alex start 7 and end 1. They both must walk exactly k steps. Graph is like: 1-2-3-4 chain, also 2-7, 7-6. So Bob could go 1-2-3-2-7? That's 4 steps. Alex could go 7-6-7-2-1? That's 4 steps. But need equal steps. Could they avoid collisions? Possibly. But BFS would tell. In sample, answer is -1, so no such routes exist. So BFS will find none.

    Now sample3: Output given: k=6, Bob: 1 2 3 4 3 2 7; Alex: 7 6 7 2 1 5 1. Let's verify: Both have 6 steps (7 nodes). Check collisions: Time0: Bob 1, Alex 7 (OK) Time1: Bob 2, Alex 6 (OK) Time2: Bob 3, Alex 7 (OK) Time3: Bob 4, Alex 2 (OK) Time4: Bob 3, Alex 1 (OK) Time5: Bob 2, Alex 5 (OK) Time6: Bob 7, Alex 1 (OK) So no same node at same time. They cross? At time2->3: Bob 3->4, Alex 7->2, no crossing on same edge? Actually 3-4 and 7-2 are different edges. At time1->2: Bob 2->3, Alex 6->7, fine. At time3->4: Bob 4->3, Alex 2->1, ok. At time4->5: Bob 3->2, Alex 1->5, ok. At time5->6: Bob 2->7, Alex 5->1, ok. There is no crossing on same edge. It's fine.

    Now BFS should find k=6 minimal. Let's try to see if any k=5 possible? Possibly not.

    Now complexity: 4m^2 = 400 million worst-case. But typical Codeforces problems with n=500, m=10000, O(n^3) might be okay (125 million). 400 million might be a bit high but can be optimized with early pruning, using bitsets? Another approach: Since we only need to avoid states where a==b, we could also do BFS in such a way that we iterate over neighbors of a and then for each neighbor b' of b. If the adjacency lists are sorted or can be iterated quickly, it's okay.

    But we can also reduce by noticing that the transition is symmetric: The pair (a,b) is unordered in a sense? Not exactly, because Bob and Alex have fixed start and end, so order matters.

    Maybe we can precompute for each node its adjacency list. The BFS will explore edges only once per state.

    Potential optimization: Use bitsets for neighbor checks to speed up enumeration? Not needed.

    Given Python's slower speed, 400 million operations is likely too slow. But we can implement in C++ with careful loops, maybe using vector adjacency lists. 400 million is borderline but might be acceptable if optimized and with low constant. But I've seen many Codeforces solutions for this problem (I think it's CF 59E? Actually this problem looks like "Bertown roads"? Not sure). I recall a problem "Friends and Berries" or something. Let's search memory: There is a Codeforces problem "Two Paths" perhaps? Actually it's from Codeforces Round #... Problem called "Two Routes" maybe? I think I've seen something similar: problem 1100D? Not that.

    Given the constraints, typical solution uses BFS on pairs of nodes with n<=500, so O(n^3) or O(n*m) etc. Let's estimate: In worst case m=10000, sum of degrees = 20000. Then sum_{a,b} deg(a)*deg(b) = (20000)^2 = 400 million. But we can avoid iterating over all pairs because BFS only visits states reachable. However, worst-case reachable could be all pairs if the graph is well-connected. With m=10000, graph can be fairly dense but not complete. Could we have all pairs reachable? Possibly, if the graph is connected enough. So worst-case BFS might need to explore many states. But maybe we can bound the number of transitions actually processed.

    Let's consider that for each state (a,b), we will consider deg(a)*deg(b) neighbor pairs. However, we can reduce by noticing that if we process states in BFS order, we mark visited states, so each state is processed only once. So total operations = sum_{(a,b) visited} deg(a)*deg(b). This sum can be large.

    But perhaps we can prune the inner loop by early skipping of states already visited? Not without checking each neighbor pair.

    Another trick: Since we only care about transitions to unvisited states, we could for each state (a,b) iterate over neighbors of a and for each neighbor a', we iterate over neighbors of b and check if (a',b') is unvisited. That is the straightforward.

    If we use C++ and simple loops, 400 million operations might run in about 1-2 seconds if optimized (each operation simple integer checks). But we also have overhead of queue and array accesses. It could be okay.

    But we also need to store parent pointers. For each state, we need to store previous state (two ints). That's 250k * 2 * 4 bytes = 2 MB. Good.

    Now, we can implement BFS with two arrays for distances (short integer maybe). Since k could be up to something? Possibly up to large? But we don't need distance large; we can use int.

    But we also need to store visited/parent. We can store parent as pair<int,int> parent[n+1][n+1] or two separate arrays: parent_a[n+1][n+1], parent_b[n+1][n+1]. Use vector<vector<pair<short,short>>>? Actually indices up to 500, so we can use short for node indices. But we can just use int.

    Better: Use a 2D array of struct {int prev_a, prev_b; char visited;}. But we need to distinguish unvisited.

    Simplify: Use distance array as vector<vector> dist(n+1, vector(n+1, -1)). And parent as vector<vector<pair<int,int>>> par(n+1, vector<pair<int,int>>(n+1, {-1,-1})).

    But this uses O(n^2) memory, which is okay.

    Now BFS queue: use queue<pair<int,int>>.

    But with n=500, 250k states, queue operations fine.

    Now we need to be careful with loops to avoid TLE.

    Potential optimization: Instead of iterating over all neighbor pairs for each state, we can precompute for each node the list of neighbors, and also maybe the adjacency matrix to quickly check if an edge exists? Not needed.

    But we can also invert the loops: For each a' neighbor of a, we can iterate over b' neighbor of b. That's okay.

    But we can also attempt to use BFS from both sides simultaneously? Not necessary.

    Given the problem seems known, I think many contestants solved it with BFS on state graph. So it's likely intended.

    Let's also consider if there is a more clever solution: Since both need to go from 1 to n and n to 1 with equal steps, the minimal steps could be something like the shortest path length L for Bob (or Alex) but they may need to add detours to avoid collisions. The BFS captures that.

    Let's think about sample3: Bob's shortest path from 1 to n is 2 (1-2-7). Alex's shortest from n to 1 is also 2. But collisions at 2. They needed to take longer routes (6 steps) to avoid. So BFS found minimal possible equal length.

    Thus BFS approach is correct.

    Now before coding, we need to confirm that BFS indeed finds the minimal k with the constraint that both must move each step (they cannot stay). In our model, each transition corresponds to both moving exactly one step. So good.

    Now check if there is any scenario where a solution exists but BFS fails because they could "meet" on a node at same time but then both continue? That's not allowed. So BFS correctly discards those.

    Now about memory: dist array of size (n+1)*(n+1) = 251001, each int 4 bytes, ~1 MB. parent array similar with two ints per cell = 2 MB. visited bool maybe. So total < 10 MB.

    Now one nuance: We should ensure that the BFS doesn't consider transitions where a' == b' which is forbidden. So we skip those.

    Now we should also ensure that start state (1,n) is not with 1 == n? n≥2 so ok.

    Now we need to output paths. In reconstruction, we need to output Bob's route and Alex's route. The routes are sequences of crossroads they pass by, including start and end. So we need to output k+1 integers for each.

    Edge Cases: The BFS might find a path of length 0? That would mean (1,n) equals (n,1) -> 1==n, impossible.

    Now test on sample3 manually with BFS? Not needed.

    Now I will code in C++.

    But before that, let's double-check that we haven't missed any constraints: The problem says "select such that the number of streets in it is the least possible." So BFS gives minimal steps.

    Now we need to output any optimal solution. So BFS with parent pointers yields one.

    Now confirm if there's any condition about meeting on crossroads when one arrives and the other leaves at same exact time? As argued, in discrete model they are not both at the same node at integer times if they cross, but consider scenario: Bob at node x, Alex at node x? That's forbidden. So fine.

    Now about the statement: "They are moving simultaneously with equal speeds, i.e. it is possible that when one of them reaches some of the crossroads, the other one leaves it." This indicates that if Bob reaches v at time t, Alex leaves v at time t, it's okay. In discrete terms, that means state at time t: Bob at v, Alex at v? Actually if Bob reaches v at time t, that means after the move; so at time t, Bob is at v. If Alex leaves v at time t, that means at time t Alex is at v and then moves to another node; but if he leaves at time t, then at time t he must be at v to start moving. So they would both be at v at time t. That would be a collision. Wait the phrase is ambiguous: "when one of them reaches some of the crossroads, the other one leaves it." This scenario could be interpreted as: At the same moment, one arrives, the other departs. That would mean they are both at the crossroad at the same instant? Actually if you think of continuous motion: If two people are at a crossroad, one is just arriving, the other is just departing, at that exact moment they are both at the crossroad. But if they are exactly at the same point at the same moment, that is meeting at the crossroad, which the problem says is not allowed? Wait re-read: "they don't want to meet at any of the crossroads, but they can meet in the middle of the street, when passing it in opposite directions." So meeting at a crossroad is forbidden. So the scenario of one arriving exactly as the other leaves would be a meeting at the crossroad? Possibly they consider that as allowed because they don't meet; they just cross at the crossroad at the same time? In typical modeling, if two people are at the same point at the same time, they meet. But the problem statement says "it is possible that when one of them reaches some of the crossroads, the other one leaves it." That suggests that this situation is allowed. So maybe they consider that they do not meet because one is just arriving and the other is just leaving, and they don't stay together. But physically they are both at the crossroad at the same instant. However, the problem might allow it because it's like they pass each other at the crossroad (like crossing at a junction). But the problem explicitly says they can meet in the middle of the street when passing in opposite directions. That refers to meeting on a street. It does not explicitly say that meeting at a crossroads when one arrives and the other leaves is forbidden. Actually the statement: "they don't want to meet at any of the crossroads" could be interpreted as they should not be at the same crossroad at the same moment. But the later example "it is possible that when one of them reaches some of the crossroads, the other one leaves it" seems to contradict that if we take strict interpretation. So maybe the intended meaning is that they cannot be both present at a crossroad at the same time unless one is just arriving and the other is just leaving? But they gave that as an example of allowed scenario? Let's parse: "They are moving simultaneously with equal speeds, i.e. it is possible that when one of them reaches some of the crossroads, the other one leaves it." This is a separate clause explaining that they move simultaneously; it might be just illustrating that they can cross at a crossroads? Actually let's read the full paragraph: "The guys are moving simultaneously with equal speeds, i.e. it is possible that when one of them reaches some of the crossroads, the other one leaves it. For example, Alex can move from crossroad 1 to crossroad 2, while Bob moves from crossroad 2 to crossroad 3."

    The example: Alex moves 1->2, Bob moves 2->3. At the start of the move: Alex at 1, Bob at 2. At the end: Alex at 2, Bob at 3. So at the moment Alex reaches crossroads 2, Bob leaves crossroads 2 (since he was at 2 at start and moves to 3). So at the end of move, Alex is at 2, Bob is at 3. They are not both at 2 at the same integer time. However, at the continuous time during the move, Bob left 2 at time 0 (immediately) and Alex arrived at 2 at time 1. So they are not at 2 at the same continuous time either. So the phrase might be describing that they can exchange positions via a node without both being there at same time. So it's consistent with our model: they avoid being at same node at same integer time. Because in that example, they never share a node at integer times. So it's fine.

    Thus BFS model is correct.

    Now let's think about potential pitfalls:

    • The BFS state space includes nodes with a=b? Not allowed. So we skip those states.

    • Could there be a scenario where the BFS finds a path but the reconstructed routes are not simple (i.e., they may contain cycles)? That's allowed because they can revisit nodes. So it's fine.

    • Could there be a scenario where the BFS path yields sequences where Bob's path is not a valid simple walk? It will be valid because each step uses an edge.

    • The BFS ensures both move each step; they cannot stay. So fine.

    Now, we must ensure the BFS doesn't run out of memory or time.

    Now code details:

    We'll implement:

    int n, m; vector adj[501];

    struct State { int a, b; };

    queue q; int dist[501][501]; pair<int,int> parent[501][501]; // store previous state

    Initialize dist with -1.

    dist[1][n] = 0; parent[1][n] = {-1, -1}; q.push({1,n});

    while (!q.empty()) { auto [a,b] = q.front(); q.pop(); if (a == n && b == 1) break; // optional, but we can continue to fill BFS but we want shortest, so break when we pop the goal (since BFS ensures shortest) for (int na : adj[a]) { for (int nb : adj[b]) { if (na != nb && dist[na][nb] == -1) { dist[na][nb] = dist[a][b] + 1; parent[na][nb] = {a,b}; q.push({na,nb}); } } } }

    if (dist[n][1] == -1) { cout << -1 << endl; } else { int k = dist[n][1]; cout << k << endl; // reconstruct vector bob_path(k+1), alex_path(k+1); int a = n, b = 1; for (int i = k; i >= 0; i--) { bob_path[i] = a; alex_path[i] = b; auto [pa, pb] = parent[a][b]; a = pa; b = pb; } // output for (int i = 0; i <= k; i++) cout << bob_path[i] << " "; cout << endl; for (int i = 0; i <= k; i++) cout << alex_path[i] << " "; cout << endl; }

    But we need to be careful: parent of start state (1,n) is (-1,-1). In reconstruction, we set a,b to (n,1) and iterate down to i=k down to 0. At i=0 we set bob_path[0] = value at time0? Let's verify: At final step i=k, we have state (n,1). So bob_path[k] = n, alex_path[k] = 1. Then we get parent of (n,1) which is previous state (a_{k-1}, b_{k-1}). So after assignment and update, we go to previous state. So after loop, we have set all entries. At the last iteration (i=0), we set bob_path[0] = a, alex_path[0] = b, where a,b are the state at time 0, which should be (1,n). Then we try to get parent of (1,n) which is (-1,-1) and assign a,b = -1. But after that we exit loop; we don't use a,b further. So it's okay.

    But we need to handle the case where parent for start state is (-1,-1) and we access it after the loop? Actually we assign bob_path[0] and then we call parent[a][b] where (a,b) is (1,n). That yields (-1,-1). Then we set a,b to -1,-1. Then loop ends because i becomes -1. That's fine. However, we must ensure that parent[1][n] is set to something like (-1,-1). Good.

    Now test with sample 1: adj[1]={2}, adj[2]={1}. BFS: start (1,2). For a=1, na=2; b=2, nb=1; na!=nb, dist[2][1] becomes 1, parent (1,2). Then q has (2,1). Next pop (2,1): a=n? Actually (2,1) is goal? n=2 so goal is (2,1). So we break. dist[2][1]=1. Reconstruction: k=1. i=1: bob_path[1]=2, alex_path[1]=1; parent[2][1]=(1,2); set a=1,b=2; i=0: bob_path[0]=1, alex_path[0]=2; parent[1][2]=(-1,-1) and we set a,b=-1,-1. Output: bob: 1 2, alex:2 1. Good.

    Now sample 2: we need to test if BFS returns -1.

    Now consider if there is any path where BFS would find a solution but it violates "they cannot stay without moving". In our transition, each step both move to adjacent nodes, so they always move. Good.

    Now about the requirement: "Until both guys reach their destinations, none of them can stay without moving." Means they must keep moving each step until both have arrived. In our model, they keep moving for exactly k steps, and at step k they both arrive at destinations simultaneously. However, what if one arrives earlier than the other? The requirement says "Until both guys reach their destinations, none of them can stay without moving." So they must continue moving until both have arrived. That implies that they both must reach their destinations at exactly the same time (the same step). Because if one reaches earlier, it would have to stay idle (or keep moving? It could keep moving away from its destination, but then it wouldn't have reached its destination yet. Actually "reach their destinations" means being at the destination crossroad. So if Bob reaches n at step t < k, then for steps > t until k, Bob would be at n? But he cannot stay; he must move each step. He could move away from n and then later come back? That would mean he hasn't reached his destination and stayed there, but he could pass through n and later come back to n at step k. But "until both guys reach their destinations, none of them can stay without moving" implies that at any step before both have finally arrived (i.e., before the final step where both are at their destinations), they must move. So it's allowed for a player to visit their destination earlier and then leave, as long as they ultimately end at the destination at the final step. However, our model requires that at step k, both are at their destinations. It does not forbid that one of them visits his destination earlier. But does the problem allow that? The problem statement: "Find for Alex and Bob such routes with equal number of streets that the guys can follow these routes and never appear at the same crossroads at the same time." And "Until both guys reach their destinations, none of them can stay without moving." That seems to allow revisiting the destination earlier, as long as they keep moving. However, there might be a nuance: The routes are defined as sequences of crossroads passed by each guy. The route is from start to destination; they can pass through the destination earlier and then leave, but then the route would end at a later time not at the destination? Actually the route should be from start to destination. If Bob passes through n at time t, then continues to other nodes and later returns to n at time k, the route would include n twice; but the route is defined as the crossroads passed by Bob from start to finish. It's acceptable that he passes through n multiple times? Typically a route is a path from start to destination; it might be not simple. But does the problem require that the last node is the destination? Yes, they say "Bob's route, i.e., the numbers of k+1 crossroads passed by Bob." It starts at 1 and ends at n after k steps. So the last node must be n. But he could pass through n earlier and then later return to n; but then his last node is n, but the path would include n earlier as well; that's allowed because it's just a list of nodes he passes. However, does the problem implicitly assume that once a guy reaches his destination, he stops? Usually in such problems, they stop when they reach destination. But here they say "Until both guys reach their destinations, none of them can stay without moving." This implies that they continue moving until both have reached; so a player might reach his destination earlier but must keep moving because the other hasn't reached yet. So he must leave the destination. That is allowed. So our model of paths where both end at the destination at the final step, but earlier steps may include the destination, is correct. So BFS allows that: state (n, x) for some x is allowed as long as x != n (since a!=b condition). But is it allowed for Bob to be at n before final step? Yes, as long as Alex is not at n at same time. And Bob must continue moving, so from n he must go to a neighbor. So that's fine.

    Now, does the BFS allow that? Yes, because we don't have any special condition forbidding a=n before final step. The goal state is only (n,1). So we can have intermediate states where a=n but b != 1, as long as we can later transition to (n,1). But can we transition from a=n to something else? From state (n, b), we can move Bob to a neighbor a' (since he must move). But that would take him away from n. Then later he must return to n at final step. That's allowed.

    Thus BFS is correct.

    Now we need to ensure that our BFS transition doesn't have any restriction that prohibits moving from a=n to neighbor, etc. So it's fine.

    Now what about the condition that they must both move each step, which we enforce by requiring a move to neighbor (they cannot stay). Good.

    Now test with a scenario: n=2, edge 1-2. Could there be a solution with k=3? Bob: 1-2-1-2, Alex:2-1-2-1. Check collisions: times: 0: (1,2), 1: (2,1) -> collision? Actually (2,1) at time1: Bob 2, Alex 1 -> allowed (they are not at same node). 2: (1,2) again; 3: (2,1). So no collisions? At time1 they are at (2,1) which is not same node. But does this violate the "both must reach destinations"? At final step k=3, Bob at 2 (good), Alex at 1 (good). So this is a valid solution of length 3? But the problem asks for minimal length. Since there is a solution of length 1, we output that. So BFS would find 1.

    Now consider a case where only odd-length solutions exist? Possibly, but BFS would find shortest.

    Now think about correctness of BFS with regard to the condition "until both reach destinations, none can stay without moving". In our BFS, we enforce that at every step both move. But if one reaches his destination earlier, does the problem require that he keep moving? Yes. So it's okay to move away. But what about if both have reached their destinations earlier than the final step? That would mean both are at (n,1) before step k. But then they would have to keep moving because they are not allowed to stay. But if both are at destinations and they must move, they would leave, and then at final step they need to be at destinations again. That could happen if they both leave and come back. But is that allowed? The requirement says "Until both guys reach their destinations, none of them can stay without moving." If both have already reached at some time t < k, then after that, they have both reached their destinations. Does the condition still require them to move? The phrase "until both guys reach their destinations, none of them can stay without moving." It could be interpreted as: As long as at least one has not reached, both must keep moving. But once both have reached, they could stop? But the route definition says they have a route of exactly k streets. So if they both reach earlier, they could theoretically stop, but the problem forces them to have exactly k steps, so they'd have to continue moving. However, the condition "until both guys reach their destinations, none of them can stay without moving" may imply that before both have reached, they cannot stay idle. After both have reached, perhaps they could stop? But they still have to have exactly k steps; if they stopped, they'd be staying, which would be disallowed by the condition? Actually the condition says "Until both guys reach their destinations, none of them can stay without moving." This only restricts the period before both have arrived. After both have arrived, there is no restriction (but then the movement would have ended, because they've arrived). However, the route length k is chosen; they must take exactly k steps. If they both arrive earlier, then for the remaining steps, they would have to either stay or move. But if they stay, that would violate the "none of them can stay without moving" only if that period is before both arrived? Actually at the moment both have arrived, the condition no longer applies, but then they would have to take additional steps after both have arrived, which would mean they are moving away from destinations, thus they are no longer at their destinations. So it's contradictory: if they both arrive at time t, then for steps t+1 onward, they are not at destinations. So they haven't both reached at those times. So the condition would again apply because at time t+1, they are not both at destinations. So the phrase "until both guys reach their destinations" likely means that for all times t before the time when both have finally arrived (i.e., before the end of the process), they must keep moving. Since at the final step they both arrive, there is no step after. So it's fine. So our model is correct.

    Thus BFS is appropriate.

    Now need to ensure we output the routes as per sample formatting: They have spaces after each integer, even trailing space? Typically it's okay. We can output without trailing space but it's accepted.

    Now about the BFS implementation: In C++, using vector adj[501]; will hold neighbors.

    Now we need to be careful about memory usage of dist and parent arrays. We can use int dist[501][501] = {-1}; but we need to initialize all to -1. For simplicity, we can use vector<vector> dist(n+1, vector(n+1, -1)). That's fine.

    Parent can be a pair<int,int> par[501][501]; but we need to set default to (-1,-1). Could do pair<int,int> par[501][501]; and use memset? Not trivial for pairs. We can initialize in loop after declaration? We can just define and rely on uninitialized values but we set parent for start and visited states; for unvisited states we won't read. However, during reconstruction, we'll read parent for only visited states. But we need to ensure that parent for start state is set to (-1,-1) and for all visited states we set; for unvisited we don't access. So we can just not initialize the whole parent array, but it's safer to initialize to zeros or -1. We'll do vector<vector<pair<int,int>>> parent(n+1, vector<pair<int,int>>(n+1, {-1,-1})).

    Now complexity: BFS might process up to 250k states, each state up to (deg(a)*deg(b)) neighbors. We can try to optimize inner loop by breaking early? Not possible.

    Potential optimization: Instead of iterating over all neighbor pairs for each state, we could precompute all possible moves? Not necessary.

    But we can perhaps use BFS and prune by checking if a and b are not too high-degree? Not.

    Maybe we can implement BFS with bitsets for neighbors to quickly find unvisited neighbor pairs? Not needed.

    Given typical Codeforces time limits, I've seen problems with n=400 and product BFS passing. So n=500 should be okay.

    Let's test with worst-case scenario: m=10000, average degree 40. Suppose degrees are evenly distributed? Then sum_{a,b} deg(a)*deg(b) = (20000)^2 = 400 million. If BFS visits all states, that's 400 million inner loop iterations. In C++, 400M is borderline but might pass with optimized code (e.g., using arrays, simple loops, O2 optimization). However, we can attempt to reduce by considering that for each state (a,b), we can iterate over a's neighbors, and for each a', we iterate over b's neighbors. If many states have high product, it's heavy. But we can also reorder loops to maybe use adjacency list of b and pre-check visited? Not.

    We can also consider using a technique: For each state (a,b), we can generate all a' and for each a', we can iterate over b' and check if dist[a'][b'] is -1. That's what we do.

    Maybe we can use a fast visited check using bitset? For each a', we have a bitset of visited states for all b'? But we need to know if (a',b') is visited. That's just an array lookup.

    Could we use BFS from both sides (bidirectional BFS)? That could reduce number of states expanded, but still worst-case might be half. But implementing bidirectional BFS on state graph with product transitions might be more complex, but doable. However, maybe not necessary.

    Let's check typical time: I've solved similar problem "Two Buttons" etc. I recall a CF problem "Robot Collision"? Not.

    But I've seen "Friends" problem from Codeforces Round #... Actually I recall a problem "Friends and Berries" but that's different.

    Another approach: Since the graph is undirected, the condition that they cannot be at same node at same time essentially means we need to find two paths of equal length that are "vertex-avoiding" in terms of simultaneous occupancy, which is like finding a shortest walk in the product graph avoiding diagonal. So BFS is natural.

    Given constraints, I'll implement BFS.

    But we need to be careful about the case where n=500 and m=10000, but the graph might be such that many states are reachable. For example, a graph that is a complete bipartite? Not possible because m limited.

    Consider worst-case: All edges are between a set of nodes? Actually we can make the graph dense: connect first 200 nodes as a clique. With 200 nodes, max edges in clique is 200*199/2 = 19900 > 10000, so we can have about 142 nodes fully connected? Let's approximate: For a clique of size k, edges = k(k-1)/2. Set equal to 10000, solve k≈141.5. So we can have a clique of 141 nodes fully connected, plus the rest isolated or something. Then degrees of nodes in clique are about 140, others 0. So many states (a,b) where both a and b are in the clique will have deg about 140, product ~19600. And there are about (141)^2 ≈ 20k such states. So sum of deg products over those states is about 20k * 19600 = 392M, which is similar to 400M. So indeed worst-case could be near 400M.

    Now if BFS visits all those 20k states (which could be reachable), we would do ~400M inner iterations. That's a lot but might be borderline. We can consider some micro-optimizations:

    • Use int arrays for dist and parent. Use flattened indexing for dist: dist[a][b] = dist[a*n + b] maybe, but 2D is fine.

    • Use adjacency lists as vector; iterate with for(int na : adj[a]) etc.

    • Use local variables for dist, parent, adj to reduce pointer dereferencing.

    • Use queue as simple queue, but pair<int,int> is okay.

    • Use early termination when we reach goal.

    • Use C++ fast I/O.

    • Possibly use short ints for distances? Not necessary.

    We can also prune by noticing that if a' == b', skip. That's a simple check.

    Maybe we can also store visited as a separate boolean array to avoid -1 checks? dist==-1 check is fine.

    Maybe we can invert loops: For each na, we can loop over nb. The inner loop will do a lot of checks. But we can maybe reduce by using the fact that for a given b, its neighbor list may be large. Could we precompute for each b a bitset of its neighbors? Then for each na, we could compute possible b'? Not simpler.

    Another thought: Since n is only 500, we could precompute adjacency matrix as bool edge[501][501] to quickly check if a node is neighbor. But we need neighbor lists anyway.

    Maybe we can implement BFS using BFS over states as standard. I think it will pass.

    But to be safe, we can also add a heuristic: If the graph is large and BFS expands many states, we can break inner loops early if we have already found goal? Not needed.

    Alternatively, we could treat the problem as finding shortest path in directed graph where vertices are (a,b) with a != b. This is essentially a graph with up to n*(n-1) states (since a != b). That's about 500*499 = 249,500. Number of edges: For each state, we have deg(a)*deg(b) outgoing edges. So total edges in product graph could be huge, but we are not building them explicitly.

    We can also reduce by considering symmetry? Not.

    I recall a known Codeforces problem: "Bob and Alice are leaving home" maybe? Actually I think it's problem 347C? Not.

    Given the problem statement, I've seen solutions online with BFS on pairs.

    Thus I'll implement BFS.

    But wait: There is a subtle nuance: The routes must have equal number of streets. In BFS, we enforce that both move each step, and the number of steps is equal. That's fine.

    Now we also need to verify that the reconstructed Bob path and Alex path indeed are sequences of crossroads passed. In our reconstruction, we stored Bob's node at each time step. That's correct.

    Now we must ensure that the paths are valid walks: For each consecutive pair of nodes in Bob's path, there must be an edge. This will hold because we only transition along edges.

    Now a potential issue: Could the BFS path have a state where at some time step, they are at (a,b) and next step to (a',b'), but if a'==b', we skip, so it's fine. However, what about the scenario where they cross on the same edge: that corresponds to a'=b and b'=a, which is allowed. So that is included as a transition (since a' = neighbor of a = b, and b' = neighbor of b = a). So it's okay.

    Now let's double-check sample3 with our BFS. We'll not test manually.

    Now we should also consider if there's any possibility of a solution that involves one person waiting (staying) but the condition forbids staying until both reach destinations. So waiting not allowed. So BFS is correct.

    Thus final solution.

    But wait: The problem statement: "Until both guys reach their destinations, none of them can stay without moving." This could be interpreted as they cannot pause at any time before both have reached their destinations. So they must move every step. So BFS's requirement that they move each step is correct.

    Now we might need to consider if they could "stay" at a node if they have reached their destination early? The condition says "until both guys reach their destinations, none of them can stay without moving." If one has reached his destination early, but the other hasn't, then the condition still applies because both have not reached destinations. So he cannot stay; he must move away. So our BFS correctly forces movement.

    Now final step: coding.

    Potential improvements for memory: Use short for distances? Not necessary.

    Now I'll write the code.

    Implementation steps:

    1. Read n,m.

    2. Create adjacency list vector adj[n+1].

    3. For i in 1..m: read u,v, add both ways.

    4. Create dist as 2D vector of int, initialized to -1.

      • We can use array of arrays: int dist[501][501]; and initialize with memset? But memset works for -1? memset sets bytes, -1 sets all bits to 1, which for int is -1 if int is 4 bytes? Yes, memset( dist, -1, sizeof(dist) ) sets each byte to 0xFF, resulting in int value -1 (if two's complement). That's fine. But we must ensure that dist is defined as int dist[501][501]; However, 5015014 = about 1M, okay. We'll do that.

      However, we need to be careful with indexing from 1 to n. We can declare as dist[501][501]; and use memset.

      Parent array: pair<int,int> parent[501][501]; We don't need to initialize all. We'll set parent for start and then for each visited. But during reconstruction we only access visited states, so uninitialized values not accessed. However, for safety we can initialize with {0,0} using memset? Not possible for pair. We'll use vector or array with default values.

      Since n<=500, we can use static arrays: pair<int,int> par[501][501]; then inside BFS we set par[na][nb] = {a,b}; For uninitialized entries we won't read. So it's okay.

      But if we use memset to set dist to -1, we can use int dist[501][501];.

    5. BFS.

    Pseudo:

    int dist[501][501]; memset(dist, -1, sizeof(dist)); queue<pair<int,int>> q; dist[1][n] = 0; q.push({1,n}); pair<int,int> par[501][501]; // will be set later par[1][n] = {-1,-1};

    while (!q.empty()) { auto [a,b] = q.front(); q.pop(); if (a == n && b == 1) break; for (int na : adj[a]) { for (int nb : adj[b]) { if (na != nb && dist[na][nb] == -1) { dist[na][nb] = dist[a][b] + 1; par[na][nb] = {a,b}; q.push({na,nb}); } } } }

    if (dist[n][1] == -1) { cout << -1 << endl; return 0; }

    int k = dist[n][1]; vector bob(k+1), alex(k+1); int a = n, b = 1; for (int i = k; i >= 0; i--) { bob[i] = a; alex[i] = b; auto [pa, pb] = par[a][b]; a = pa; b = pb; }

    cout << k << endl; for (int i = 0; i <= k; i++) cout << bob[i] << " "; cout << endl; for (int i = 0; i <= k; i++) cout << alex[i] << " "; cout << endl;

    Now we must ensure that we include <bits/stdc++.h> and using namespace std;.

    Now check for possible integer overflow? No.

    Now edge: The BFS may break early when popping goal, but we need to ensure that we have set parent for goal. That's done when we first push it into queue. So breaking after pop is fine because BFS ensures shortest distance when we first encounter? Actually we set distance when we push, and we break when we pop. Since BFS is FIFO, the first time we pop the goal, its distance is minimal. But we could also break when we set distance for goal (i.e., when we discover it) but that would also be fine; however, breaking on pop is safe because we know all nodes at that distance are popped after all nodes at distance-1 are popped. So the first time we encounter goal either in discovery or pop, distance is minimal. But if we break on pop, it's after we have processed nodes at distance d-1, and we might have already discovered goal at distance d from some node, but not yet popped. However, we could have break when we set dist[goal] to d. But we need parent already set. I'll break on pop for simplicity.

    Now we must ensure that we do not skip processing other states because we break early but that's fine.

    Now potential issue: The BFS may take long to reach goal if many states. But we need to process all until we pop goal; that's the BFS.

    Now let's think about potential improvements: The inner loops could be optimized by precomputing adjacency lists as arrays (C++ vectors) and using const references.

    Implementation details:

    • Use for (int na : adj[a]) { for (int nb : adj[b]) { ... } }

    Now memory: par[501][501] each element is pair<int,int> = 8 bytes, total ~2MB.

    dist[501][501] int = 1MB.

    Queue size up to states ~250k, each pair 8 bytes = 2MB.

    All fine.

    Now we need to handle reading input quickly: use ios_base::sync_with_stdio(false); cin.tie(NULL).

    Now test with sample1.

    I will test mentally.

    Now sample2: BFS will not reach (7,1). Dist remains -1.

    Now sample3: BFS will find k=6.

    Now we might want to test additional cases.

    Edge case: n=500, m=0? But m>=1. Graph may be disconnected. If no path from 1 to n for Bob alone, obviously no solution. But BFS would also not find path.

    Now consider case where Bob and Alex could have same path lengths but they cannot avoid collisions; BFS will find if there is any.

    Now I'll think about correctness in more depth: The BFS transitions allow any simultaneous moves. However, is there any additional constraint that they cannot meet at the same crossroad at the same time when one arrives and the other leaves exactly at that crossroad? In our model, that would correspond to a state where at time t, both are at same node? Let's examine the scenario: Bob arrives at v at time t (so after move), Alex leaves v at time t (so before move, Alex is at v; after move, Alex is at some neighbor). For them to be at same node at the same instant, we need to consider continuous time. Suppose at time t (integer), after move, positions are defined. Usually, in discrete-time modeling, we consider that at integer times, each person is at a node. If we define that at time t, they are at nodes after completing the t-th move (or before first move at time 0). This is standard. Then the scenario "one arrives, the other leaves" would have: at time t, Bob is at v (since he just arrived), but Alex was at v at time t? Actually Alex leaves v at time t: if he leaves v at time t, at time t he should be at v (since he hasn't moved yet), then he moves during the interval (t, t+1) to neighbor, arriving at t+1. But that means at time t, Alex is at v. So at time t, both Bob and Alex would be at v, if Bob is also at v at time t. So that would be a collision. But is that scenario allowed according to the problem? The problem says "it is possible that when one of them reaches some of the crossroads, the other one leaves it." They gave example: Alex moves 1->2, Bob moves 2->3. Let's see: At time 0: Alex at 1, Bob at 2. At time 1: Alex at 2, Bob at 3. In this example, at time 1, Alex reaches crossroads 2, Bob leaves crossroads 2? At time 1, Bob is at 3, not at 2. So Bob left 2 at time 0? Actually Bob left 2 at time 0 (since he started at 2 and moved to 3). So the phrase "when one of them reaches some of the crossroads, the other one leaves it" might refer to the situation where the reaching happens at time t+1 and the leaving happens at time t. In the example, Alex reaches 2 at time 1, Bob leaves 2 at time 0. So they are not at the same node at the same integer time. So the phrase might be describing the relationship across time steps, not simultaneous. So it's consistent: The condition only forbids being at same node at same integer time. So our model is correct.

    Thus BFS is good.

    Now we should also confirm that BFS does not need to check anything about crossing on edges causing them to meet at the same time at a node if they cross exactly at a node? That's already covered.

    Now we can implement.

    But there is one more nuance: The problem says "they can meet in the middle of the street, when passing it in opposite directions." This is allowed. In our model, if they cross on an edge (a,b) -> (b,a), then at the half-step they meet. That's allowed. So BFS permits it.

    Now we must ensure that we are not missing any condition that prevents them from being on the same edge at the same time going in same direction? Actually if they are on same edge in same direction, they could meet? That would require same node at same time? Not necessarily; they could be following each other; they never meet. But could that cause a problem? They could be on the same edge at same time, one behind the other. Is that allowed? The problem doesn't forbid being on the same street at the same time, only meeting at crossroads is forbidden. They could be on same street as long as they don't meet. However, if they are on same edge moving in same direction, they will not meet unless one catches up, but they have equal speeds so if they start at same time from different nodes, they could be on the same edge at the same time? For example, Bob at node 1, Alex at node 2, edge 1-2. If Bob moves 1->2 and Alex moves 2->3 (different edge), they don't share edge. If both move along same edge in same direction, they'd start from same node? Actually if both move from node 1 to node 2, they'd start at same node at time t, which is forbidden (a_t = 1, u_t = 1? Actually if both start at same node, they'd be colliding at start). If they start at different nodes and move onto the same edge in same direction, e.g., Bob at node 1 moves to 2, Alex at node 2 moves to 3? Not same edge. For them to be on same edge in same direction, they'd need one to be behind the other on the same edge: e.g., Bob at node 1 at time t, Alex at node 2 at time t, edge 1-2. If Bob moves 1->2 and Alex stays? Not allowed. If Alex moves 2->1, they cross. If Alex moves 2->3, they use different edges. So it's impossible for both to be on the same edge at same time moving same direction without one having started from the node that the other is moving to? Let's analyze: Suppose at time t, Bob at node A, Alex at node B. At time t+1, they move to A' and B'. For them to be on the same edge (the same unordered pair of nodes) at some point during the movement, they would have to traverse the same edge. That means either (A,A') = (B,B') (same edge, same direction) or (A,A') = (B',B) (crossing). Crossing is allowed. Same direction would require that A = B and A' = B'. But A = B would be a collision at time t (since they would be at same node). So same direction sharing an edge implies collision at start, which is forbidden. Thus we don't need to worry about it; our BFS does not explicitly forbid moving along the same edge in same direction because it would require starting from same node, which is already forbidden (a == b). So it's automatically avoided.

    Thus BFS is complete.

    Now let's test on a simple case where they must cross to avoid collision: n=3, edges: 1-2, 2-3. Bob from 1 to 3, Alex from 3 to 1. Shortest paths: 1-2-3 and 3-2-1. They would collide at 2 at time 1. Could they take longer routes? Graph is a path. Bob: 1-2-1-2-3 (4 steps), Alex: 3-2-1-2-1? But Alex must end at 1. He could do 3-2-1-2-1? That would be 4 steps? Let's check: 3-2 (1), 2-1 (2), 1-2 (3), 2-1 (4). That ends at 1. Bob: 1-2 (1), 2-1 (2), 1-2 (3), 2-3 (4). Check collisions: Time0: (1,3) ok. Time1: (2,2)? Bob 2, Alex 2 -> collision (time1). So that fails. Could they offset? Bob: 1-2-3-2-3 (4 steps) ends at 3, Alex: 3-2-1-2-1 (4 steps) ends at 1. Check: t0: (1,3) ok. t1: (2,2) collision? Bob 2, Alex 2? Yes, because Alex goes 3->2, Bob 1->2. So collision. Bob: 1-2-1-2-3 (4), Alex: 3-2-3-2-1 (4): t0 (1,3); t1 (2,2) again collision. It seems any path of length 2 (or even) will cause them to meet at 2 at time1 if they both go through 2? Because the graph is a path, any route from 1 to 3 must pass through 2 at some point. Similarly for 3 to 1. Because the only route. If they take longer routes, they'll still have to pass through 2. Could they avoid being at 2 at the same time? They could coordinate such that when Bob is at 2, Alex is not at 2. For example, Bob: 1-2 (t1), Alex: 3-2 (t1) would collide. But if Bob delays arriving at 2 until after Alex has left? But Alex must also leave 2 to go to 1 eventually. They could schedule: Bob arrives at 2 at time 1, Alex leaves 2 at time 1? That would be the crossing scenario: Bob 1->2, Alex 2->1, then at time1 Bob at 2, Alex at 1, so not colliding. That's actually the crossing scenario on edge 1-2. Wait: Bob 1->2, Alex 2->1: At time0: Bob at 1, Alex at 2. Time1: Bob at 2, Alex at 1. That's the crossing on edge (1,2). That's allowed. But note that Alex's destination is 1, so he arrives at 1 at time1. But the route length would be 1 step, which is the minimal. But we already know they collide? Actually earlier we thought they collide because if both take the direct path 1-2-3 and 3-2-1, at time1 they would be at 2 and 2. But if they take direct crossing, Bob's path would be 1-2-3? That's two steps, not one. The crossing scenario we just described is Bob: 1->2, Alex: 2->1, but that doesn't get Bob to 3 or Alex to 1? Actually Alex ends at 1 after step1, good. Bob ends at 2, not at 3. So not complete. So they need more steps. Could they do: Bob: 1-2 (step1), then 2-3 (step2). Alex: 3-2 (step1), then 2-1 (step2). That yields at time1: Bob 2, Alex 2 -> collision. So they can't. Could they do: Bob: 1-2 (1), 2-1 (2), 1-2 (3), 2-3 (4). Alex: 3-2 (1), 2-3 (2), 3-2 (3), 2-1 (4). Check collisions: t0: (1,3) ok; t1: (2,2) collision because Alex at 2, Bob at 2. So fails. Could they do: Bob: 1-2 (1), 2-3 (2), 3-2 (3), 2-3 (4) ends at 3? That ends at 3? Actually 2-3 at step4 ends at 3, so Bob path: 1,2,3,2,3 (length 4). Alex: 3-2 (1), 2-1 (2), 1-2 (3), 2-1 (4) ends at 1. Check times: t0: (1,3); t1: (2,2) collision. So fails. Could they offset so that Bob is at 2 when Alex is not? Perhaps if they cross on edge 2-3? For Bob to go from 1 to 3, he must be at 2 at some times. Alex must be at 2 at some times. To avoid same time, they could be at 2 at different times. However, because they both start at opposite ends and must end at opposite ends, maybe parity forces them to be at 2 at same time if the path length is even? Let's see. In a path graph of 3 nodes, the positions of Bob and Alex as functions of time have parity constraints. Since the graph is bipartite? Actually nodes 1 and 3 are even distance from 2? 1 and 3 are both at distance 1 from 2, so same parity? The graph is bipartite: partition {1,3} and {2}. Moves flip partition each step. Bob starts at 1 (partition A), after odd steps at 2 (partition B), after even steps at 1 or 3 (partition A). Alex starts at 3 (partition A), after odd steps at 2 (B), after even steps at 1 or 3 (A). So both start in A. To end, Bob must end at 3 (A) and Alex at 1 (A). Since both start and end in A, the number of steps must be even (because to go from A to A you need even number of steps). So k is even. At odd time steps, both are in B (i.e., node 2). At time 1, they both are in B, so they must both be at node 2 (since only node in B). So collision unavoidable. Thus no solution. So answer -1. BFS would confirm.

    Thus BFS would correctly find no path.

    Now our BFS will process states and eventually not reach (3,1) because maybe reachable but with a=b? Actually state (3,1) is goal. But we might reach (2,2) and other states, but is (3,1) reachable? Let's try BFS: start (1,3). Neighbors: a' can be 2 (neighbor of 1), b' can be 2 (neighbor of 3). So (2,2) is reachable but forbidden (a'==b') so we skip. Any other? a' = 2 only, b' = 2 only. So no other neighbor. So no transition. So (3,1) unreachable. So BFS returns -1. Good.

    Now we see that for the path graph of length 2 (3 nodes), BFS correctly determines impossibility.

    Now for more complex graphs, BFS works.

    Now we need to think about the possibility of the BFS using too much time because of many neighbor pairs. We could attempt to prune loops where deg(a) or deg(b) is zero. But they are at least 1 if they are reachable from start? Possibly some nodes have degree 0 but not likely if they are reachable from start.

    We could also implement BFS with a twist: Instead of enumerating all neighbor pairs for each state, we could treat the moves as independent and use BFS on layered graph: For each state (a,b), we can move to (a',b') if there's an edge a-a' and b-b'. That's the same.

    Given that n=500 and m=10000, worst-case product sum ~400M. Let's estimate time: In C++, 400M operations might be about 2 seconds on a fast machine? Actually typical CF server can do about 1e8-2e8 operations per second? It's around 3e8 operations per second for simple loops? Not exactly; usually around 1e8-2e8 for simple integer operations. 400M might be 2-4 seconds, might be near the limit. But we might get lucky. However, we can try to reduce constant.

    Possible optimization: Use adjacency list stored as vector and use iterators. Could also use plain arrays and sizes. But it's fine.

    But we can also consider using a technique: Since we only need the shortest path, we could use BFS with bitset to speed up neighbor enumeration? For each a, we have a bitset of neighbors. Then for a given state (a,b), we can compute the set of possible (a',b') as neighbor bitset of a AND something? Actually we need pairs. Not helpful.

    Another idea: Use BFS from both sides: bidirectional BFS. That would reduce the number of states explored roughly by square root. Since the branching factor is high, exploring from both ends could drastically reduce the number of states expanded. Because we would search from start and from goal (n,1) simultaneously. When we meet, we have solution. However, bidirectional BFS in implicit graph with high branching factor can be beneficial. But we need to keep track of distances and parents from both sides. Also the graph is directed? Actually state graph is directed? The transitions are symmetric because edges are undirected and moves are simultaneous, so if we reverse the direction of time, we get similar transitions: from (a,b) we can go to (a',b') if edges a-a' and b-b'. Reverse transition from (a',b') to (a,b) is also allowed (since edges are undirected). So the graph is undirected (each transition is reversible). So bidirectional BFS is possible. But we also need to reconstruct the path. That's more complex but doable: we can store parent pointers from start and from goal (reverse direction). When we find a meeting state, we combine paths.

    But implementing bidirectional BFS for product graph may be more code but could be faster. But maybe not necessary.

    Given the time, I'll start with simple BFS and see if it passes. I think it will, as I've seen similar solutions.

    But before finalizing, let's verify that we correctly interpret the input and output format: In samples, they have a trailing space after each line of numbers. It's fine.

    Now I'll produce the code.

    Potential bug: The BFS may not find a path if the start state (1,n) is forbidden? 1 != n, so ok.

    Now, consider if the graph has nodes with degree 0? If 1 or n has degree 0, then no path. BFS will finish with dist[n][1] = -1.

    Now, we must ensure that we treat nodes correctly: adjacency lists for nodes 1..n inclusive.

    Now memory for dist: use int dist[501][501]; but 501501 is about 251001. But if we use memset(dist, -1, sizeof dist), it sets all bytes to 0xFF, which for int is -1. However, we need to ensure that the array is contiguous and we are not using too much stack memory? 501501*4 = 1,004,004 bytes ~ 1 MB. That's fine for stack? In C++, local arrays of that size inside main may be too large for stack? Usually stack size is around 8 MB, so 1 MB is okay. But we also have parent array of pair<int,int> (8 bytes each) => 2 MB, total 3 MB local, still okay. However, some judges may have smaller stack, but typically it's fine. To be safe, we can allocate them as global variables (static) to be on data segment, not stack. Let's declare them global to avoid stack overflow. Or use vectors. I'll use global arrays to be safe.

    Thus:

    const int MAXN = 501; vector adj[MAXN]; int dist[MAXN][MAXN]; pair<int,int> parent[MAXN][MAXN];

    In main, we'll fill adj, then set dist to -1 using memset? For global arrays, they are zero-initialized if not initialized. But we need -1. We can use memset inside main for dist, but for parent we can just set as needed.

    Alternatively, we can use vector<vector> for dist and vector<vector<pair<int,int>>> for parent, which allocate on heap. That's also fine. Let's use vectors for simplicity and to avoid global variables? But vectors have overhead, but it's fine.

    But for performance, raw arrays may be faster. I'll use global arrays.

    Now BFS queue: queue<pair<int,int>> q.

    Now implement:

    int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; for (int i=0; i<m; ++i) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } memset(dist, -1, sizeof(dist)); queue<pair<int,int>> q; dist[1][n] = 0; parent[1][n] = {-1,-1}; q.push({1,n}); while (!q.empty()) { auto [a,b] = q.front(); q.pop(); if (a == n && b == 1) break; for (int na : adj[a]) { for (int nb : adj[b]) { if (na != nb && dist[na][nb] == -1) { dist[na][nb] = dist[a][b] + 1; parent[na][nb] = {a,b}; q.push({na,nb}); } } } } if (dist[n][1] == -1) { cout << -1 << endl; return 0; } int k = dist[n][1]; vector bob(k+1), alex(k+1); int a = n, b = 1; for (int i = k; i >= 0; i--) { bob[i] = a; alex[i] = b; auto p = parent[a][b]; a = p.first; b = p.second; } cout << k << endl; for (int i = 0; i <= k; i++) cout << bob[i] << " "; cout << endl; for (int i = 0; i <= k; i++) cout << alex[i] << " "; cout << endl; return 0; }

    Now test with sample1:

    Input: 2 1 1 2

    Adj[1]={2}, adj[2]={1} dist[1][2]=0, q: (1,2) Pop (1,2): a=1,b=2; neighbors: na=2, nb=1 => (2,1) na!=nb, dist[2][1] becomes 1, parent set. push (2,1) Next pop (2,1): a=2,b=1 -> break. k=1, reconstruct: a=2,b=1; i=1: bob[1]=2, alex[1]=1; parent[2][1] = (1,2) set earlier? We set parent[2][1] when we discovered it, yes. Then p = (1,2). a=1,b=2; i=0: bob[0]=1, alex[0]=2; parent[1][2] is (-1,-1). Good. Output correct.

    Sample2: Should output -1.

    Sample3: Should output given.

    Now consider potential issues: In sample3, the BFS may find a path of length 6. We'll trust.

    Now we should also consider if there is a possibility that BFS could find a path but the reconstruction yields sequences that do not respect the edge condition due to some bug? For each step, we stored states; the step from (a_prev,b_prev) to (a,b) is valid because we only added transitions that are edges. So sequences are valid.

    Now check if the BFS might produce a solution where at some time they are at same node? No, because we skipped states where na==nb. And start state is ok.

    Now we also need to ensure that BFS does not consider transitions where (a,b) is such that a==b? Actually we never push such states because we skip when na==nb. But could we ever start with a state where a==b? No.

    Now what about the case where the goal (n,1) itself has n==1? Not allowed because n>=2.

    Now we should test a simple case: n=3, edges: 1-2, 2-3, 1-3 (triangle). Bob 1->3, Alex 3->1. Shortest direct: Bob 1-3 (1 step), Alex 3-1 (1 step). But at time0: (1,3) ok; after step: (3,1) ok; they never meet at same node; also they could cross on edge? Actually they both use edge 1-3? But they are moving opposite directions? Bob from 1 to 3, Alex from 3 to 1, so they cross on edge 1-3, which is allowed. So there is a solution with k=1. But is that allowed? They meet in the middle of street, allowed. So BFS should find. Our BFS: start (1,3). neighbors: for a=1: neighbors 2,3; for b=3: neighbors 1,2. Consider pairs: (2,1) na=2, nb=1 -> (2,1) na!=nb, dist[2][1]=1, push. (2,2) skip, (3,1) na=3, nb=1 -> (3,1) na!=nb, dist[3][1]=1, push. So both (2,1) and (3,1) are discovered. The goal (3,1) is discovered with distance 1. So BFS finds k=1. Good.

    Now what about a case where the graph has multiple edges? Not allowed.

    Now we should also consider the possibility of timeouts. Let's attempt to roughly estimate the number of operations for worst-case graph. Suppose we have a clique of size about 141, as before. Then total states reachable might be around (141)^2 = 20k (since states with nodes outside clique might not be reachable if start and goal are inside clique? But start is 1, goal is n. We could set 1 and n to be in the clique. So reachable states may be all pairs of nodes within the clique? Possibly also some outside if there are edges from clique to outside. But if the clique is 141 nodes, there may be many edges to outside? With m=10000, if we have a clique of 141, edges inside = 141*140/2 = 9870, leaving 130 edges for connections to outside. So many nodes could be isolated or loosely connected. Then the reachable state space could include also some outside nodes. But likely the majority of reachable states will be within the clique because the graph is dense there. So about 20k states. For each such state, deg(a) and deg(b) are about 140 (if both in clique). So product about 19600. So total neighbor checks = 20k * 19600 = 392M. That's the worst-case scenario we considered. That's about 4e8 checks. Each check involves a few operations: if condition, array accesses. Could be borderline but might still pass with optimized C++ (maybe ~0.5-1 second per 100M operations? On modern CPU, 4e8 operations could be about 2-3 seconds, which might be okay if time limit is 2 seconds? It's close. Let's see typical Codeforces time limit for this problem? I'm not sure. But we can attempt to micro-opt.

    Optimization ideas:

    • Use int& d = dist[a][b] to avoid repeated lookups? Not needed.

    • Use local references for adjacency lists: const auto& neighA = adj[a]; const auto& neighB = adj[b]; then nested loops.

    • Use plain for loops with indices to avoid range-based overhead? Probably minimal.

    • Use early exit: if (a == n && b == 1) break; after pop.

    • Could break early inside loops if we found goal? Actually we can check after setting a new state if it's goal, then we can break out of both loops and then out of BFS. But that only saves time if goal is found early. In worst-case, goal may be deep, but BFS may still expand many states.

    • Use "if (dist[na][nb] == -1)" which involves accessing memory. Could we store visited as a separate bitset to speed? Not needed.

    • Use "if (na != nb)" is cheap.

    • Could we reduce product by iterating over neighbors of a and for each na, iterate over neighbors of b but skip those equal to na? That's already done.

    Another thought: We can precompute for each node the list of neighbors plus maybe also include itself? Not.

    One more optimization: Because we skip states where na == nb, we could, for each na, iterate over nb and skip nb == na. If degrees are large, skipping a few cases doesn't reduce much.

    Maybe we can reorder loops: For each na, we check if dist[na][*] is visited? Not.

    Alternatively, we can use BFS with edge-based transitions: Instead of iterating over all nb for each na, we could do something like: For each na, we can mark that from state (a,b) we can move to any (na, nb) where nb neighbor of b. But we can't compress.

    Given that I want to be safe, I can implement bidirectional BFS. But let's first analyze if simple BFS is enough.

    Search memory: I think I've seen this problem on Codeforces: it's problem "Friends" from Codeforces Round #276 (Div. 1) maybe? Let me recall: There's problem "Friends and Subsequences"? Not.

    Let's try to google mental: "Bertown" appears in many problems. I recall a problem "Bertown roads" which is about orienting edges. Not.

    But I do remember a problem "Two Paths" with constraints n,m up to 500,10000 and requiring two walks that avoid meeting, solved with BFS on pairs. Actually I've seen editorial for CF 59C? Not.

    Anyway, I think BFS is intended.

    But I'll check if there is any possibility to reduce complexity by noting that we only need states with a != b. That we already do.

    Maybe we can store dist as short to reduce memory bandwidth? Not.

    Alternatively, we can use BFS with queue of ints encoded as a*501+b to flatten index. But that's similar.

    Given time, I'll code simple BFS and see if it passes. If it fails, we can think of optimization.

    But to be thorough, let's attempt to implement a more optimized version:

    • Use arrays of vectors for adjacency.

    • Use int dist[501][501]; memset to -1.

    • Use pair<short,short> parent[501][501] to save memory? Not necessary.

    • Use queue with pair<int,int>.

    • Use for loops with indices: for (int i = 0; i < (int)adj[a].size(); i++) { int na = adj[a][i]; ... } Might be slightly faster than range-based.

    • Precompute degrees in array deg[] and maybe store adjacency in a 2D array of bits? Not.

    We'll do:

    const int N = 501; vector adj[N]; int dist[N][N]; pair<int,int> parent[N][N]; // could be short, but int is fine

    In main, after reading input:

    memset(dist, -1, sizeof(dist));

    queue<pair<int,int>> q; dist[1][n] = 0; parent[1][n] = {-1,-1}; q.push({1,n});

    while (!q.empty()) { int a = q.front().first, b = q.front().second; q.pop(); if (a == n && b == 1) break; for (int na : adj[a]) { for (int nb : adj[b]) { if (na != nb && dist[na][nb] == -1) { dist[na][nb] = dist[a][b] + 1; parent[na][nb] = {a,b}; q.push({na,nb}); // optional: if (na == n && nb == 1) goto found; but break loops. } } } }

    But to break out quickly after discovering goal, we could check after setting and then break out of loops and then out of BFS. However, since BFS processes in order, when we first set goal, it's at distance d, and we could immediately stop because BFS guarantees shortest path. But we need to ensure that we don't miss shorter path? Actually when we first set goal, it is the first time we encounter it, and it must be the shortest because BFS expands layers. However, could there be another path of same length that sets goal at the same distance but we haven't processed it yet? But since BFS processes nodes in order, when we first discover goal, we have not yet processed any node at distance d (since we discovered it while processing a node at distance d-1). So it's the shortest distance. So we can break as soon as we set dist[n][1] != -1. That could save time because we wouldn't need to process remaining nodes in queue. So we can add:

    if (na == n && nb == 1) { // we have found goal dist[n][1] = dist[a][b] + 1; parent[n][1] = {a,b}; // we can break all loops and then exit BFS. }

    But we need to break out of nested loops and then the outer while. We can use a flag or goto.

    Implement:

    bool found = false; while (!q.empty() && !found) { auto [a,b] = q.front(); q.pop(); for (int na : adj[a]) { for (int nb : adj[b]) { if (na == n && nb == 1 && dist[na][nb] == -1) { dist[na][nb] = dist[a][b] + 1; parent[na][nb] = {a,b}; found = true; break; } if (na != nb && dist[na][nb] == -1) { dist[na][nb] = dist[a][b] + 1; parent[na][nb] = {a,b}; q.push({na,nb}); } } if (found) break; } }

    But note that we may also discover goal through the normal path; if we discover it in the inner loop, we can stop BFS. However, we must also ensure we don't miss pushing other states that could lead to goal at same distance? Not necessary because we already have a shortest path. So we can break early.

    This early termination could save time, especially if the goal is found quickly. In worst-case where solution doesn't exist or goal is deep, we still explore all reachable states. But early termination won't help worst-case.

    Now, for worst-case where no solution exists, BFS will explore all reachable states, which could be many. Could that happen? Possibly if graph is such that (n,1) unreachable, BFS explores all states reachable from (1,n) under constraints. That could be many. So worst-case we still might process many states.

    But maybe for most graphs where solution exists, BFS finds it relatively early. However, we should handle the worst-case.

    Maybe we can improve by using BFS from both ends. But that might be overkill.

    Let's think about complexity more: sum_{a,b visited} deg(a)*deg(b) can be large but maybe we can reduce by noticing that deg(a) and deg(b) are limited. For each state, we iterate through all neighbors of a and b. However, if we precompute for each node a list of neighbors, but we can also precompute for each pair (a,b) the set of possible moves? Not.

    We could also note that we only need to consider pairs (na, nb) where na != nb. So we can skip when na == nb. But that's a small fraction.

    Another thought: Instead of iterating over all neighbor pairs, we could treat the transition as: from state (a,b) we can go to any state where Bob moves to a neighbor, and Alex moves to a neighbor, but we can separate the moves: This is essentially a product of two independent moves. So we could BFS by exploring Bob's moves and Alex's moves separately? Not.

    Maybe we can do BFS on Bob's path while tracking the set of nodes Alex could be at each step, ensuring no collision. That could be like DP: dp[step][a][b] but that's same.

    Given that n is 500, we could attempt to use Floyd–Warshall like? Not.

    Alternatively, we could model it as a shortest path in a graph where nodes are (a,b) and edges have cost 1. That's BFS.

    I think BFS will pass.

    But let's try to estimate more precisely: 400 million loops. In C++, a simple loop with two condition checks and array accesses might take about 1-2 ns? Actually typical C++ does about 0.5-1 ns per simple operation? Not exactly. Usually, 1e8 operations can be done in about 0.3 seconds if very simple, but with memory accesses it can be slower. However, 4e8 might be 1-2 seconds. But if we have vector iterators, maybe a bit slower.

    We can test by writing a small program that simulates worst-case: two nested loops with 20k outer and inner 20k? Not exactly.

    But maybe we can improve by using adjacency lists and caching some info.

    Another optimization: Since we repeatedly access dist[na][nb], we might suffer from cache misses. The dist array is large (1M entries) but that's okay; each access is random though because na and nb vary. That might cause many cache misses.

    We could reorder loops to improve locality? For a fixed a, na varies over neighbors of a, and for each na, we iterate over nb which are neighbors of b. That accesses dist[na][nb] with na fixed across inner loop? Actually for a fixed a and b, we have outer loop over na (neighbors of a), inner over nb (neighbors of b). So for each na, we access dist[na][*] for many nb. That may cause locality because for a fixed na, the row dist[na] is accessed sequentially across nb? But nb varies over neighbors of b, which are not necessarily contiguous. However, the dist array is stored row-major; dist[na][nb] accesses row na, column nb. So if we fix na and iterate over nb values, we are accessing different columns within the same row. If nb values are random, it's random accesses within a row. But row length is 501, which fits in cache? 501 ints = 2KB, which might fit in L1 cache? L1 cache is typically 32KB, so a row of 501 ints is 2KB, so for each na, the entire row could be cached if we access many columns? But nb values are the neighbor list of b, which may be unsorted. We could sort adjacency lists to improve locality? Not necessary.

    But we could iterate over nb first, then na? Then for each nb, we access dist[*][nb] columns, which are across rows, causing more cache misses. So the current order (na outer, nb inner) is better because we have row locality.

    Thus we keep that.

    We can also pre-sort adjacency lists so that neighbor indices are increasing, which might improve cache prefetch? Not huge.

    Now, what about visited checks? dist[na][nb] is int; reading -1 is cheap.

    We can also store visited as a separate bool array to reduce checking? Not.

    Now, we can maybe reduce the inner loop by noting that we can prune if na == nb quickly. That's done.

    Given everything, I'll proceed with BFS.

    Now before finalizing, I'll think about possible alternative solutions.

    The problem essentially asks for two walks of equal length from 1 to n and from n to 1 that are node-disjoint at same times. This is similar to finding a directed path in the product graph avoiding the diagonal.

    Could there be a polynomial time algorithm using max flow? Possibly modeling as a time-expanded network? But that would be like BFS anyway.

    Thus BFS is fine.

    Now, we should also consider that the answer might be -1 if there is no path. BFS will handle.

    Now we also need to ensure we handle the case where there is a solution but the BFS might find a path where they meet on a node at same time due to some oversight? Already prevented.

    Now I'll implement and test with sample cases.

    But there's a nuance: The BFS state (a,b) represents the positions at the same time after some number of steps. However, we must also ensure that they never meet at a node at the same time during the entire walk. We only check at integer times. As argued, that's sufficient because meeting at a node at fractional times would require them to be at that node at same integer time? Let's think: Could they meet at a node at a non-integer time without being there at integer times? Suppose Bob moves from node u to v along edge of length 1, Alex moves from w to v along edge w-v. They could both arrive at v at time exactly 0.5? For them to both be at v at the same moment, they would have to start at different times or have different speeds? But they move simultaneously with equal speeds. If they both start at time 0 from u and w respectively, and the distances from u to v and w to v are both 1, they will both arrive at v at time 1 (if they move continuously). So arrival time is at integer times if edges have unit length and they start at time 0. Because they move at speed 1 unit per time step, so moving along an edge of length 1 takes exactly 1 time unit. So they are at nodes only at integer times. Thus the only times they can be at nodes are integer times. So indeed collisions only occur at integer times. So our discrete model is exact.

    Thus BFS is exact.

    Now finalize.

    But wait: What about meeting at a node exactly at time 0? Start state is (1,n) which are distinct. Good.

    Now we need to ensure that we don't produce paths where Bob and Alex are at same node at the same time because we only skip states where na == nb, but we also need to skip the start state if 1 == n, but that's false.

    Now additional check: Could they meet at same node at time t if the transition leads to same node but we also need to check the state after move? We skip that. Good.

    Now about the reconstruction: We backtrack using parent pointers. Ensure that parent for start is set to (-1,-1). In the loop, after setting a,b = pa,pb, for i=0 we set bob[0] and alex[0] and then try to access parent[1][n] which is (-1,-1). That's fine.

    Now we should output k as the number of streets, which is number of steps.

    Now test with sample3 manually? Let's quickly simulate with code mentally? Not necessary.

    Now potential bug: The BFS might use a lot of memory for parent storing -1 for all cells, but we only need for visited. Using global array of pairs, uninitialized cells contain garbage. But we only access parent for visited states (since we only set parent when we set dist). So it's safe.

    Now about using memset on dist: dist is global so it's zero-initialized? Actually global variables are zero-initialized. So if we don't memset, dist will be 0 for all entries. But we need -1 to indicate unvisited. We could use 0 as unvisited? But then start state distance is 0, so we need another sentinel. Could use -1. So we need to set all to -1. Using memset with -1 works because it sets all bytes to 0xFF, resulting in int -1. But careful: global variables are zero-initialized before dynamic initialization? Actually if we declare global int dist[501][501]; it is zero-initialized at program start. Then we call memset(dist, -1, sizeof(dist)), which overwrites with -1. That's fine.

    Alternatively, we could use a vector and assign -1.

    Now we need to ensure that the BFS queue does not overflow. It will hold up to visited states (max 250k), fine.

    Now implement.

    After coding, I'll test with some custom cases.

    I will also think about the possibility that there is a solution with k=0? Not possible because start != goal.

    Now I'll produce final answer.

    But before final, let's run through sample3 manually to see if BFS yields exactly the given paths or some other. Not important.

    Now produce final code.

    Potential improvements: Use short for node indices in parent to save memory? Not needed.

    Now code.

    One more thought: The BFS could be implemented with two queues to handle distance levels, but not needed.

    Now final answer. ```cpp

    #include #include #include #include using namespace std;

    const int MAXN = 501; vector adj[MAXN]; // adjacency lists int dist[MAXN][MAXN]; // -1 = not visited, else distance from start pair<int, int> parent[MAXN][MAXN]; // previous state (a_prev, b_prev)

    int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // initialise distance array
    memset(dist, -1, sizeof(dist));
    
    queue<pair<int, int>> q;
    dist[1][n] = 0;
    parent[1][n] = {-1, -1};
    q.push({1, n});
    
    bool found = false;
    while (!q.empty() && !found) {
        auto [a, b] = q.front();
        q.pop();
        // explore all simultaneous moves
        for (int na : adj[a]) {
            for (int nb : adj[b]) {
                if (na == nb) continue;               // meeting at crossroad forbidden
                if (dist[na][nb] != -1) continue;    // already visited
                dist[na][nb] = dist[a][b] + 1;
                parent[na][nb] = {a, b};
                if (na == n && nb == 1) {            // reached the goal
                    found = true;
                    break;
                }
                q.push({na, nb});
            }
            if (found) break;
        }
    }
    
    if (dist[n][1] == -1) {
        cout << -1 << '\n';
        return 0;
    }
    
    int k = dist[n][1];
    vector<int> bob(k + 1), alex(k + 1);
    int a = n, b = 1;
    for (int i = k; i >= 0; --i) {
        bob[i] = a;
        alex[i] = b;
        auto [pa, pb] = parent[a][b];
        a = pa;
        b = pb;
    }
    
    cout << k << '\n';
    for (int i = 0; i <= k; ++i) cout << bob[i] << " ";
    cout << '\n';
    for (int i = 0; i <= k; ++i) cout << alex[i] << " ";
    cout << '\n';
    
    return 0;
    

    }