# Cat and Mouse **Difficulty:** HARD [External](https://leetcode.com/problems/cat-and-mouse) Canonical: https://scaleengineer.com/dsa/problems/cat-and-mouse **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory) **Algorithms:** [Topological Sort](https://scaleengineer.com/algorithms/topological-sort) **Data structures:** Graph --- ## Problem A game on an **undirected** graph is played by two players, Mouse and Cat, who alternate turns. The graph is given as follows: `graph[a]` is a list of all nodes `b` such that `ab` is an edge of the graph. The mouse starts at node `1` and goes first, the cat starts at node `2` and goes second, and there is a hole at node `0`. During each player's turn, they **must** travel along one edge of the graph that meets where they are. For example, if the Mouse is at node 1, it **must** travel to any node in `graph[1]`. Additionally, it is not allowed for the Cat to travel to the Hole (node `0`). Then, the game can end in three ways: * If ever the Cat occupies the same node as the Mouse, the Cat wins. * If ever the Mouse reaches the Hole, the Mouse wins. * If ever a position is repeated (i.e., the players are in the same position as a previous turn, and it is the same player's turn to move), the game is a draw. Given a `graph`, and assuming both players play optimally, return * `1` if the mouse wins the game, * `2` if the cat wins the game, or * `0` if the game is a draw. **Example 1:** ![](https://assets.glich.co/dsa/cat-and-mouse/image0.jpg) **Input:** graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]] **Output:** 0 **Example 2:** ![](https://assets.glich.co/dsa/cat-and-mouse/image1.jpg) **Input:** graph = [[1,3],[0],[3],[0,2]] **Output:** 1 **Constraints:** * `3 <= graph.length <= 50` * `1 <= graph[i].length < graph.length` * `0 <= graph[i][j] < graph.length` * `graph[i][j] != i` * `graph[i]` is unique. * The mouse and the cat can always move. # Approaches ## Value Iteration This approach uses a technique called value iteration. It's a form of dynamic programming where we repeatedly update the value (outcome) of each game state based on the values of the states it can transition to. We start by identifying the definite win/loss states (terminal states) and consider all other states as potential draws. Then, we loop through all states, refining their outcomes based on whether a player can force a win or is forced into a loss. This process continues until the outcomes for all states stabilize. **Time:** O(N^5) in the worst case. The number of states is O(N^2). The loop can run up to O(N^2) times (the number of states that can change color). Inside the loop, we iterate over all O(N^2) states, and for each, we check its neighbors, which takes O(N) time. This gives a total complexity of O(N^2 * N^2 * N) = O(N^5). · **Space:** O(N^2), where N is the number of nodes. This is for the `color` table which stores the outcome for each pair of mouse/cat positions and turn. **Pros:** Conceptually straightforward, as it directly models the iterative nature of determining game outcomes.; Avoids the complexity of managing recursion stacks and explicit cycle detection. **Cons:** Significantly less efficient than the BFS-based approach due to repeated re-evaluation of states.; The number of iterations required for convergence can be large, proportional to the number of states, leading to a high overall time complexity. ### Explanation The core idea is to model the game as a state graph and iteratively determine the outcome of each state. A state is defined by `(mouse_position, cat_position, turn)`. We maintain a 3D array, `color`, to store the outcome for each state: `0` for Draw, `1` for Mouse Win, and `2` for Cat Win. Initially, we set the outcomes for the terminal states: any state where the mouse is at node 0 is a win for the mouse, and any state where the cat and mouse are on the same node is a win for the cat. All other states are initialized to Draw. The algorithm then enters a loop. In each pass, it attempts to update the color of each undecided state based on the colors of its successor states. For a player to win from a state, they must have at least one move to a state that results in a win for them. For a player to lose, all of their possible moves must lead to states where the opponent wins. If neither of these conditions is met, the state's outcome remains a draw for that iteration. This iterative process continues until a full pass over all states results in no changes to the `color` array. At this point, the outcomes have converged, and we can return the outcome for the initial state `(mouse=1, cat=2, turn=MOUSE)`. ```java class Solution { private static final int DRAW = 0; private static final int MOUSE_WIN = 1; private static final int CAT_WIN = 2; public int catMouseGame(int[][] graph) { int n = graph.length; int[][][] color = new int[n][n][2]; // Initialize terminal states for (int i = 0; i < n; i++) { for (int t = 0; t < 2; t++) { if (i > 0) { color[0][i][t] = MOUSE_WIN; // Mouse at hole color[i][i][t] = CAT_WIN; // Cat catches mouse } } } while (true) { boolean changed = false; // Iterate over all non-terminal states for (int m = 1; m < n; m++) { for (int c = 1; c < n; c++) { if (m == c) continue; for (int t = 0; t < 2; t++) { if (color[m][c][t] != DRAW) continue; if (t == 0) { // Mouse's turn boolean canMouseWin = false; boolean allCatWin = true; for (int next_m : graph[m]) { if (color[next_m][c][1] == MOUSE_WIN) { canMouseWin = true; break; } if (color[next_m][c][1] != CAT_WIN) { allCatWin = false; } } if (canMouseWin) { color[m][c][0] = MOUSE_WIN; changed = true; } else if (allCatWin) { color[m][c][0] = CAT_WIN; changed = true; } } else { // Cat's turn boolean canCatWin = false; boolean allMouseWin = true; for (int next_c : graph[c]) { if (next_c == 0) continue; if (color[m][next_c][0] == CAT_WIN) { canCatWin = true; break; } if (color[m][next_c][0] != MOUSE_WIN) { allMouseWin = false; } } if (canCatWin) { color[m][c][1] = CAT_WIN; changed = true; } else if (allMouseWin) { color[m][c][1] = MOUSE_WIN; changed = true; } } } } } if (!changed) { break; } } return color[1][2][0]; } } ``` ### Algorithm * Define the game state by `(mouse_position, cat_position, turn)`. * Use a 3D array, `color[N][N][2]`, to store the outcome for each state (0: DRAW, 1: MOUSE_WIN, 2: CAT_WIN). * Initialize the `color` array. All non-terminal states are initially considered DRAW (0). Terminal states are set as wins for the appropriate player: * If Mouse is at the hole (node 0), it's a MOUSE_WIN. * If Cat and Mouse are at the same node, it's a CAT_WIN. * Repeatedly iterate through all undecided states until no state's outcome changes in a full pass (i.e., the outcomes have converged). * In each iteration, for every state, re-evaluate its outcome based on the current outcomes of its successor states: * **Mouse's Turn:** The state is a MOUSE_WIN if the mouse can move to any state that is a MOUSE_WIN. It's a CAT_WIN if all possible moves lead to CAT_WIN states. Otherwise, it remains a DRAW. * **Cat's Turn:** The state is a CAT_WIN if the cat can move to any state that is a CAT_WIN. It's a MOUSE_WIN if all possible moves lead to MOUSE_WIN states. Otherwise, it remains a DRAW. * Once the `color` table stabilizes, the outcome for the starting state `(mouse=1, cat=2, turn=MOUSE)` is the answer. ## Bottom-Up DP with BFS (Coloring Algorithm) This is the most efficient approach, treating the problem as a search on the game's state graph. It works backward from the terminal states (where the game outcome is known) and uses a Breadth-First Search (BFS) to propagate these outcomes to other states. This method is often called a "coloring" algorithm. We start by "coloring" the terminal states as either a win for the Mouse or a win for the Cat. These states are added to a queue. Then, we process the queue, and for each state, we examine its "parent" states (the states that could have led to it). If a player can move from a parent state to a state that is a win for them, we color that parent state as a win. If all of a player's moves from a parent state lead to losses, we color that parent state as a loss. States that are never colored are part of a cycle where neither player can force a win, and are thus draws. **Time:** O(N^3). The number of states is O(N^2). Each state is enqueued and processed exactly once. When processing a state, we iterate through its parent states. The number of parents is bounded by the maximum degree of a node in the graph, D (where D < N). Thus, the total time complexity is O(N^2 * D), which simplifies to O(N^3). · **Space:** O(N^2), where N is the number of nodes. This space is used for the `color` table, the `degree` table, and the BFS queue. **Pros:** Highly efficient, solving the problem in a single pass over the state graph.; Guaranteed to find the optimal strategy for both players and correctly identify draws.; It is the standard and most effective algorithm for solving such impartial games with draws. **Cons:** The logic for propagating results backward from child to parent states can be complex to implement correctly.; Requires careful management of the `degree` array to correctly identify when a player is forced into a loss. ### Explanation This optimal approach uses a bottom-up dynamic programming strategy with a Breadth-First Search (BFS). We determine the outcome of states whose results are certain and propagate this information to their predecessor states. 1. **State Representation**: The state is `(mouse_pos, cat_pos, turn)`, where `turn=0` for Mouse and `turn=1` for Cat. 2. **Data Structures**: * `color[n][n][2]`: Stores the outcome (0: Draw, 1: Mouse Win, 2: Cat Win). * `degree[n][n][2]`: Stores the number of outgoing moves from a state that lead to an undecided (Draw) state. This is key to determining forced losses. * `Queue`: A queue to manage states whose outcomes have been determined, for the BFS process. 3. **Initialization**: * We first populate the `color` array and the queue with all terminal states. These are states where the mouse is at the hole (node 0) or the cat is at the same position as the mouse. * We initialize the `degree` for each state. For a mouse's turn state `(m, c, 0)`, the degree is the number of neighbors of `m`. For a cat's turn state `(m, c, 1)`, it's the number of neighbors of `c` (excluding the hole). 4. **BFS Propagation**: * We dequeue a state `(m, c, t)` whose outcome `outcome` is known. * We then find all parent states `P` that could transition into `(m, c, t)`. A parent state `P` has the opposite turn `1-t`. * For each uncolored parent state `P`: * If the player at `P` can move to `(m, c, t)` and `outcome` is a win for them, we color `P` as a win and enqueue it. This is because an optimal player will always choose a winning move. * If `outcome` is a loss for the player at `P`, we decrement `P`'s degree. If the degree becomes zero, it means all possible moves from `P` lead to a loss. Thus, `P` itself is a losing state. We color `P` as a loss and enqueue it. 5. **Result**: After the BFS completes, any state remaining with `color = 0` is a draw. The final answer is the color of the initial state `(1, 2, 0)`. ```java class Solution { private static final int DRAW = 0; private static final int MOUSE_WIN = 1; private static final int CAT_WIN = 2; public int catMouseGame(int[][] graph) { int n = graph.length; // state: (mouse_pos, cat_pos, turn), turn 0 for mouse, 1 for cat int[][][] color = new int[n][n][2]; // out-degree for each state int[][][] degree = new int[n][n][2]; // Initialize degrees for (int m = 0; m < n; m++) { for (int c = 0; c < n; c++) { degree[m][c][0] = graph[m].length; degree[m][c][1] = graph[c].length; for (int neighbor : graph[c]) { if (neighbor == 0) { degree[m][c][1]--; break; } } } } Queue queue = new LinkedList<>(); // Initialize terminal states for (int i = 1; i < n; i++) { color[0][i][0] = MOUSE_WIN; color[0][i][1] = MOUSE_WIN; queue.offer(new int[]{0, i, 0}); queue.offer(new int[]{0, i, 1}); color[i][i][0] = CAT_WIN; color[i][i][1] = CAT_WIN; queue.offer(new int[]{i, i, 0}); queue.offer(new int[]{i, i, 1}); } while (!queue.isEmpty()) { int[] state = queue.poll(); int m = state[0], c = state[1], t = state[2]; int outcome = color[m][c][t]; int prev_turn = 1 - t; if (prev_turn == 0) { // Parent state was Mouse's turn for (int prev_m : graph[m]) { if (color[prev_m][c][0] == DRAW) { if (outcome == MOUSE_WIN) { // Mouse found a winning move color[prev_m][c][0] = MOUSE_WIN; queue.offer(new int[]{prev_m, c, 0}); } else { // outcome == CAT_WIN, a losing move for Mouse degree[prev_m][c][0]--; if (degree[prev_m][c][0] == 0) { // All moves are losing color[prev_m][c][0] = CAT_WIN; queue.offer(new int[]{prev_m, c, 0}); } } } } } else { // Parent state was Cat's turn for (int prev_c : graph[c]) { if (prev_c == 0) continue; if (color[m][prev_c][1] == DRAW) { if (outcome == CAT_WIN) { // Cat found a winning move color[m][prev_c][1] = CAT_WIN; queue.offer(new int[]{m, prev_c, 1}); } else { // outcome == MOUSE_WIN, a losing move for Cat degree[m][prev_c][1]--; if (degree[m][prev_c][1] == 0) { // All moves are losing color[m][prev_c][1] = MOUSE_WIN; queue.offer(new int[]{m, prev_c, 1}); } } } } } } return color[1][2][0]; } } ``` ### Algorithm * Define the game state as `(mouse_pos, cat_pos, turn)`. * Initialize a `color[N][N][2]` array to `0` (DRAW) to store the final outcome of each state. * Initialize a `degree[N][N][2]` array to store the number of available moves for the current player from each state. * Create a queue for Breadth-First Search (BFS) and add all terminal states (where Mouse is at hole, or Cat catches Mouse). * Set the `color` for these terminal states to `MOUSE_WIN` (1) or `CAT_WIN` (2) accordingly. * While the queue is not empty, dequeue a state `S = (m, c, t)` with a determined outcome. * For each "parent" state `P` that can transition to `S`: * If `P` is already colored, skip it. * **Winning Propagation:** If the player at `P` wins by moving to `S`, color `P` with the winning outcome and enqueue `P`. * **Losing Propagation:** If moving to `S` is a losing move for the player at `P`, decrement the `degree` of `P`. If `degree[P]` becomes `0`, it means all moves from `P` are losing moves. Color `P` as a loss and enqueue `P`. * After the BFS completes, any state still colored `0` is a draw. Return `color[1][2][0]`. # Solutions ### CSharp ```csharp using System ; using System.Collections.Generic ; public class Solution { private int n ; private int [][] g ; private int [,,] ans ; private int [,,] degree ; private const int HOLE = 0 , MOUSE_START = 1 , CAT_START = 2 ; private const int MOUSE_TURN = 0 , CAT_TURN = 1 ; private const int MOUSE_WIN = 1 , CAT_WIN = 2 , TIE = 0 ; public int CatMouseGame ( int [][] graph ) { n = graph . Length ; g = graph ; ans = new int [ n , n , 2 ]; degree = new int [ n , n , 2 ]; for ( int i = 0 ; i < n ; i ++) { for ( int j = 1 ; j < n ; j ++) { degree [ i , j , MOUSE_TURN ] = g [ i ]. Length ; degree [ i , j , CAT_TURN ] = g [ j ]. Length ; } } for ( int i = 0 ; i < n ; i ++) { foreach ( int j in g [ HOLE ]) { degree [ i , j , CAT_TURN ]--; } } Queue < int [ ]> q = new Queue < int [ ]> (); for ( int j = 1 ; j < n ; j ++) { ans [ 0 , j , MOUSE_TURN ] = MOUSE_WIN ; ans [ 0 , j , CAT_TURN ] = MOUSE_WIN ; q . Enqueue ( new int [] { 0 , j , MOUSE_TURN }); q . Enqueue ( new int [] { 0 , j , CAT_TURN }); } for ( int i = 1 ; i < n ; i ++) { ans [ i , i , MOUSE_TURN ] = CAT_WIN ; ans [ i , i , CAT_TURN ] = CAT_WIN ; q . Enqueue ( new int [] { i , i , MOUSE_TURN }); q . Enqueue ( new int [] { i , i , CAT_TURN }); } while ( q . Count > 0 ) { int [] state = q . Dequeue (); int t = ans [ state [ 0 ], state [ 1 ], state [ 2 ]]; List < int [ ]> prevStates = GetPrevStates ( state ); foreach ( var prevState in prevStates ) { int pm = prevState [ 0 ], pc = prevState [ 1 ], pt = prevState [ 2 ]; if ( ans [ pm , pc , pt ] == TIE ) { bool win = ( t == MOUSE_WIN && pt == MOUSE_TURN ) || ( t == CAT_WIN && pt == CAT_TURN ); if ( win ) { ans [ pm , pc , pt ] = t ; q . Enqueue ( prevState ); } else { if (-- degree [ pm , pc , pt ] == 0 ) { ans [ pm , pc , pt ] = t ; q . Enqueue ( prevState ); } } } } } return ans [ MOUSE_START , CAT_START , MOUSE_TURN ]; } private List < int [ ]> GetPrevStates ( int [] state ) { List < int [ ]> pre = new List < int [ ]> (); int m = state [ 0 ], c = state [ 1 ], t = state [ 2 ]; int pt = t ^ 1 ; if ( pt == CAT_TURN ) { foreach ( int pc in g [ c ]) { if ( pc != HOLE ) { pre . Add ( new int [] { m , pc , pt }); } } } else { foreach ( int pm in g [ m ]) { pre . Add ( new int [] { pm , c , pt }); } } return pre ; } } ``` ### Java ```java class Solution { private int n; private int[][] g; private int[][][] res; private int[][][] degree; private static final int HOLE = 0, MOUSE_START = 1, CAT_START = 2; private static final int MOUSE_TURN = 0, CAT_TURN = 1; private static final int MOUSE_WIN = 1, CAT_WIN = 2, TIE = 0; public int catMouseGame(int[][] graph) { n = graph.length; g = graph; res = new int[n][n][2]; degree = new int[n][n][2]; for (int i = 0; i < n; ++i) { for (int j = 1; j < n; ++j) { degree[i][j][MOUSE_TURN] = g[i].length; degree[i][j][CAT_TURN] = g[j].length; } } for (int i = 0; i < n; ++i) { for (int j : g[HOLE]) { --degree[i][j][CAT_TURN]; } } Deque q = new ArrayDeque<>(); for (int j = 1; j < n; ++j) { res[0][j][MOUSE_TURN] = MOUSE_WIN; res[0][j][CAT_TURN] = MOUSE_WIN; q.offer(new int[]{0, j, MOUSE_TURN}); q.offer(new int[]{0, j, CAT_TURN}); } for (int i = 1; i < n; ++i) { res[i][i][MOUSE_TURN] = CAT_WIN; res[i][i][CAT_TURN] = CAT_WIN; q.offer(new int[]{i, i, MOUSE_TURN}); q.offer(new int[]{i, i, CAT_TURN}); } while (!q.isEmpty()) { int[] state = q.poll(); int t = res[state[0]][state[1]][state[2]]; List prevStates = getPrevStates(state); for (var prevState : prevStates) { int pm = prevState[0], pc = prevState[1], pt = prevState[2]; if (res[pm][pc][pt] == TIE) { boolean win = (t == MOUSE_WIN && pt == MOUSE_TURN) || (t == CAT_WIN && pt == CAT_TURN); if (win) { res[pm][pc][pt] = t; q.offer(prevState); } else { if (--degree[pm][pc][pt] == 0) { res[pm][pc][pt] = t; q.offer(prevState); } } } } } return res[MOUSE_START][CAT_START][MOUSE_TURN]; } private List getPrevStates(int[] state) { List pre = new ArrayList<>(); int m = state[0], c = state[1], t = state[2]; int pt = t ^ 1; if (pt == CAT_TURN) { for (int pc : g[c]) { if (pc != HOLE) { pre.add(new int[]{m, pc, pt}); } } } else { for (int pm : g[m]) { pre.add(new int[]{pm, c, pt}); } } return pre; } } ``` ### CPP ```cpp const int HOLE = 0 ; const int MOUSE_START = 1 ; const int CAT_START = 2 ; const int MOUSE_TURN = 0 ; const int CAT_TURN = 1 ; const int MOUSE_WIN = 1 ; const int CAT_WIN = 2 ; const int TIE = 0 ; class Solution { public: int catMouseGame ( vector < vector < int >>& graph ) { int n = graph . size (); int res [ n ][ n ][ 2 ]; int degree [ n ][ n ][ 2 ]; memset ( res , 0 , sizeof res ); memset ( degree , 0 , sizeof degree ); for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 1 ; j < n ; ++ j ) { degree [ i ][ j ][ MOUSE_TURN ] = graph [ i ]. size (); degree [ i ][ j ][ CAT_TURN ] = graph [ j ]. size (); } for ( int j : graph [ HOLE ]) { -- degree [ i ][ j ][ CAT_TURN ]; } } auto getPrevStates = [ & ]( int m , int c , int t ) { int pt = t ^ 1 ; vector < tuple < int , int , int >> pre ; if ( pt == CAT_TURN ) { for ( int pc : graph [ c ]) { if ( pc != HOLE ) { pre . emplace_back ( m , pc , pt ); } } } else { for ( int pm : graph [ m ]) { pre . emplace_back ( pm , c , pt ); } } return pre ; }; queue < tuple < int , int , int >> q ; for ( int j = 1 ; j < n ; ++ j ) { res [ 0 ][ j ][ MOUSE_TURN ] = res [ 0 ][ j ][ CAT_TURN ] = MOUSE_WIN ; q . emplace ( 0 , j , MOUSE_TURN ); q . emplace ( 0 , j , CAT_TURN ); } for ( int i = 1 ; i < n ; ++ i ) { res [ i ][ i ][ MOUSE_TURN ] = res [ i ][ i ][ CAT_TURN ] = CAT_WIN ; q . emplace ( i , i , MOUSE_TURN ); q . emplace ( i , i , CAT_TURN ); } while ( ! q . empty ()) { auto [ m , c , t ] = q . front (); q . pop (); int x = res [ m ][ c ][ t ]; for ( auto [ pm , pc , pt ] : getPrevStates ( m , c , t )) { if ( res [ pm ][ pc ][ pt ] == TIE ) { bool win = ( x == MOUSE_WIN && pt == MOUSE_TURN ) || ( x == CAT_WIN && pt == CAT_TURN ); if ( win ) { res [ pm ][ pc ][ pt ] = x ; q . emplace ( pm , pc , pt ); } else { if ( -- degree [ pm ][ pc ][ pt ] == 0 ) { res [ pm ][ pc ][ pt ] = x ; q . emplace ( pm , pc , pt ); } } } } } return res [ MOUSE_START ][ CAT_START ][ MOUSE_TURN ]; } }; ``` ### Python ```python HOLE , MOUSE_START , CAT_START = 0 , 1 , 2 MOUSE_TURN , CAT_TURN = 0 , 1 MOUSE_WIN , CAT_WIN , TIE = 1 , 2 , 0 class Solution : def catMouseGame ( self , graph : List [ List [ int ]]) -> int : def get_prev_states ( state ): m , c , t = state pt = t ^ 1 pre = [] if pt == CAT_TURN : for pc in graph [ c ]: if pc != HOLE : pre . append (( m , pc , pt )) else : for pm in graph [ m ]: pre . append (( pm , c , pt )) return pre n = len ( graph ) res = [[[ 0 , 0 ] for _ in range ( n )] for _ in range ( n )] degree = [[[ 0 , 0 ] for _ in range ( n )] for _ in range ( n )] for i in range ( n ): for j in range ( 1 , n ): degree [ i ][ j ][ MOUSE_TURN ] = len ( graph [ i ]) degree [ i ][ j ][ CAT_TURN ] = len ( graph [ j ]) for j in graph [ HOLE ]: degree [ i ][ j ][ CAT_TURN ] -= 1 q = deque () for j in range ( 1 , n ): res [ 0 ][ j ][ MOUSE_TURN ] = res [ 0 ][ j ][ CAT_TURN ] = MOUSE_WIN q . append (( 0 , j , MOUSE_TURN )) q . append (( 0 , j , CAT_TURN )) for i in range ( 1 , n ): res [ i ][ i ][ MOUSE_TURN ] = res [ i ][ i ][ CAT_TURN ] = CAT_WIN q . append (( i , i , MOUSE_TURN )) q . append (( i , i , CAT_TURN )) while q : state = q . popleft () t = res [ state [ 0 ]][ state [ 1 ]][ state [ 2 ]] for prev_state in get_prev_states ( state ): pm , pc , pt = prev_state if res [ pm ][ pc ][ pt ] == TIE : win = ( t == MOUSE_WIN and pt == MOUSE_TURN ) or ( t == CAT_WIN and pt == CAT_TURN ) if win : res [ pm ][ pc ][ pt ] = t q . append ( prev_state ) else : degree [ pm ][ pc ][ pt ] -= 1 if degree [ pm ][ pc ][ pt ] == 0 : res [ pm ][ pc ][ pt ] = t q . append ( prev_state ) return res [ MOUSE_START ][ CAT_START ][ MOUSE_TURN ] ```