{"problem":{"name":"Symmetric Matrix","description":{"content":"You are given an integer sequence $Y=(Y_1,Y_2,\\ldots,Y_N)$ of length $N$ where each element is between $1$ and $N$ inclusive. Determine whether there exists an $N \\times N$ integer matrix $A=(A_{i,j})","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc208_d"},"statements":[{"statement_type":"Markdown","content":"You are given an integer sequence $Y=(Y_1,Y_2,\\ldots,Y_N)$ of length $N$ where each element is between $1$ and $N$ inclusive.\nDetermine whether there exists an $N \\times N$ integer matrix $A=(A_{i,j})$ $(1\\le i , j \\le N)$ that satisfies all of the following conditions, and if it exists, find one such matrix.\n\n*   $1\\le A_{i,j} \\le N$ $(1\\le i \\le N, 1\\le j\\le N)$\n*   $A_{i,j}=A_{j,i}$ $(1\\le i\\le N, 1\\le j\\le N)$\n*   $A_{i,j_1}\\neq A_{i,j_2}$ $(1\\le i\\le N, 1\\le j_1 < j_2 \\le N)$\n*   $A_{i,Y_i}=1$ $(1\\le i\\le N)$\n\nYou are given $T$ test cases; solve each of them.\n\n## Constraints\n\n*   $1\\le T\\le 5000$\n*   $1\\le N \\le 500$\n*   The sum of $N^2$ over all test cases is at most $500^2$.\n*   $1\\le Y_i\\le N$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_1$\n$\\text{case}_2$\n$\\vdots$\n$\\text{case}_T$\n\nEach test case is given in the following format:\n\n$N$\n$Y_1$ $Y_2$ $\\ldots$ $Y_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc208_d","tags":[],"sample_group":[["4\n3\n1 3 2\n3\n1 2 3\n1\n1\n5\n1 3 2 5 4","Yes\n1 2 3\n2 3 1\n3 1 2\nNo\nYes\n1\nYes\n1 2 5 4 3\n2 3 1 5 4\n5 1 4 3 2\n4 5 3 2 1\n3 4 2 1 5\n\nConsider the first test case.\nIt can be verified that the $A$ in the sample output satisfies all conditions. Other than this, for example, the following $A$ will also be accepted:\n\n1 3 2\n3 2 1\n2 1 3"]],"created_at":"2026-03-03 11:01:14"}}