using System; using System.Collections.Generic; using System.IO; using System.Linq; using static System.Math; using System.Text; using System.Threading; using System.Globalization; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using Library; namespace Program { public static class ProblemE { static bool SAIKI = false; static public int numberOfRandomCases = 0; static public void MakeTestCase(List _input, List _output, ref Func _outputChecker) { } static public void Solve() { var N = NN; var AB = Repeat(0, N).Select(_ => new { A = NN - 1, B = NN - 1 }).ToArray(); var bs1 = 0L; var bs2 = N; var gs = bs2 + N; var st = gs + N; var go = st + 1; var flow = new LIB_MaxFlow(go + 1); for (var i = 0; i < N; ++i) { flow.AddEdge(st, bs1 + i, 1); flow.AddEdge(bs1 + i, bs2 + AB[i].A, 1); flow.AddEdge(bs1 + i, bs2 + AB[i].B, 1); flow.AddEdge(bs2 + i, gs + i, 1); flow.AddEdge(gs + i, go, 1); } var cnt = flow.Flow(st, go); if (cnt < N) Console.WriteLine("No"); else { Console.WriteLine("Yes"); var ans = new long[N]; foreach (var item in flow.GetAllEdge()) { if (item.from >= bs1 && item.from < bs2 && item.flow == 1) { ans[item.from - bs1] = item.to - bs2; } } for (var i = 0; i < N; ++i) { Console.WriteLine(ans[i] + 1); } } } class Printer : StreamWriter { public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } } public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { base.AutoFlush = false; } public Printer(Stream stream, Encoding encoding) : base(stream, encoding) { base.AutoFlush = false; } } static LIB_FastIO fastio = new LIB_FastIODebug(); static public void Main(string[] args) { if (args.Length == 0) { fastio = new LIB_FastIO(); Console.SetOut(new Printer(Console.OpenStandardOutput())); } if (SAIKI) { var t = new Thread(Solve, 134217728); t.Start(); t.Join(); } else Solve(); Console.Out.Flush(); } static long NN => fastio.Long(); static double ND => fastio.Double(); static string NS => fastio.Scan(); static long[] NNList(long N) => Repeat(0, N).Select(_ => NN).ToArray(); static double[] NDList(long N) => Repeat(0, N).Select(_ => ND).ToArray(); static string[] NSList(long N) => Repeat(0, N).Select(_ => NS).ToArray(); static long Count(this IEnumerable x, Func pred) => Enumerable.Count(x, pred); static IEnumerable Repeat(T v, long n) => Enumerable.Repeat(v, (int)n); static IEnumerable Range(long s, long c) => Enumerable.Range((int)s, (int)c); static IOrderedEnumerable OrderByRand(this IEnumerable x) => Enumerable.OrderBy(x, _ => xorshift); static IOrderedEnumerable OrderBy(this IEnumerable x) => Enumerable.OrderBy(x.OrderByRand(), e => e); static IOrderedEnumerable OrderBy(this IEnumerable x, Func selector) => Enumerable.OrderBy(x.OrderByRand(), selector); static IOrderedEnumerable OrderByDescending(this IEnumerable x) => Enumerable.OrderByDescending(x.OrderByRand(), e => e); static IOrderedEnumerable OrderByDescending(this IEnumerable x, Func selector) => Enumerable.OrderByDescending(x.OrderByRand(), selector); static IOrderedEnumerable OrderBy(this IEnumerable x) => x.OrderByRand().OrderBy(e => e, StringComparer.OrdinalIgnoreCase); static IOrderedEnumerable OrderBy(this IEnumerable x, Func selector) => x.OrderByRand().OrderBy(selector, StringComparer.OrdinalIgnoreCase); static IOrderedEnumerable OrderByDescending(this IEnumerable x) => x.OrderByRand().OrderByDescending(e => e, StringComparer.OrdinalIgnoreCase); static IOrderedEnumerable OrderByDescending(this IEnumerable x, Func selector) => x.OrderByRand().OrderByDescending(selector, StringComparer.OrdinalIgnoreCase); static string Join(this IEnumerable x, string separator = "") => string.Join(separator, x); static uint xorshift { get { _xsi.MoveNext(); return _xsi.Current; } } static IEnumerator _xsi = _xsc(); static IEnumerator _xsc() { uint x = 123456789, y = 362436069, z = 521288629, w = (uint)(DateTime.Now.Ticks & 0xffffffff); while (true) { var t = x ^ (x << 11); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); yield return w; } } static bool Chmax(this ref T lhs, T rhs) where T : struct, IComparable { if (lhs.CompareTo(rhs) < 0) { lhs = rhs; return true; } return false; } static bool Chmin(this ref T lhs, T rhs) where T : struct, IComparable { if (lhs.CompareTo(rhs) > 0) { lhs = rhs; return true; } return false; } static void Fill(this T[] array, T value) => array.AsSpan().Fill(value); static void Fill(this T[,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0], array.Length).Fill(value); static void Fill(this T[,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0], array.Length).Fill(value); static void Fill(this T[,,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0, 0], array.Length).Fill(value); } } namespace Library { class LIB_MaxFlow { public struct Edge { public int from; public int to; public long cap; public long flow; } const int SHIFT_SIZE = 30; const int MASK = 1073741823; ulong[] pos; int posCnt; int[][] gTo; int[] gToCnt; int[][] gRev; int[] gRevCnt; long[][] gCap; int[] gCapCnt; int N; public LIB_MaxFlow(long n) { N = (int)n; pos = new ulong[16]; gTo = new int[n][]; gRev = new int[n][]; gCap = new long[n][]; gToCnt = new int[n]; gRevCnt = new int[n]; gCapCnt = new int[n]; ref var gToref = ref gTo[0]; ref var gRevref = ref gRev[0]; ref var gCapref = ref gCap[0]; for (var i = 0; i < n; i++) { Unsafe.Add(ref gToref, i) = new int[16]; Unsafe.Add(ref gRevref, i) = new int[16]; Unsafe.Add(ref gCapref, i) = new long[16]; } } [MethodImpl(MethodImplOptions.AggressiveOptimization)] public int AddEdge(long from, long to, long cap) { pos[posCnt++] = ((ulong)from << SHIFT_SIZE) | (uint)gToCnt[from]; gTo[from][gToCnt[from]++] = (int)to; gRev[from][gRevCnt[from]++] = gRevCnt[to]; gCap[from][gCapCnt[from]++] = cap; gTo[to][gToCnt[to]++] = (int)from; gRev[to][gRevCnt[to]++] = gRevCnt[from] - 1; gCap[to][gCapCnt[to]++] = 0; if (posCnt == pos.Length) { var tmp = new ulong[posCnt << 1]; Unsafe.CopyBlock(ref Unsafe.As(ref tmp[0]), ref Unsafe.As(ref pos[0]), (uint)(8 * posCnt)); pos = tmp; } if (gToCnt[from] == gTo[from].Length) { { var tmp = new int[gToCnt[from] << 1]; Unsafe.CopyBlock(ref Unsafe.As(ref tmp[0]), ref Unsafe.As(ref gTo[from][0]), (uint)(4 * gToCnt[from])); gTo[from] = tmp; } { var tmp = new int[gRevCnt[from] << 1]; Unsafe.CopyBlock(ref Unsafe.As(ref tmp[0]), ref Unsafe.As(ref gRev[from][0]), (uint)(4 * gRevCnt[from])); gRev[from] = tmp; } { var tmp = new long[gCapCnt[from] << 1]; Unsafe.CopyBlock(ref Unsafe.As(ref tmp[0]), ref Unsafe.As(ref gCap[from][0]), (uint)(8 * gCapCnt[from])); gCap[from] = tmp; } } if (gToCnt[to] == gTo[to].Length) { { var tmp = new int[gToCnt[to] << 1]; Unsafe.CopyBlock(ref Unsafe.As(ref tmp[0]), ref Unsafe.As(ref gTo[to][0]), (uint)(4 * gToCnt[to])); gTo[to] = tmp; } { var tmp = new int[gRevCnt[to] << 1]; Unsafe.CopyBlock(ref Unsafe.As(ref tmp[0]), ref Unsafe.As(ref gRev[to][0]), (uint)(4 * gRevCnt[to])); gRev[to] = tmp; } { var tmp = new long[gCapCnt[to] << 1]; Unsafe.CopyBlock(ref Unsafe.As(ref tmp[0]), ref Unsafe.As(ref gCap[to][0]), (uint)(8 * gCapCnt[to])); gCap[to] = tmp; } } return posCnt - 1; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public Edge GetEdge(long i) { var idx = (int)i; var idxf = pos[idx] >> SHIFT_SIZE; var idxt = (int)(pos[idx] & MASK); var eTo = gTo[idxf][idxt]; var eRev = gRev[idxf][idxt]; var reCap = gCap[eTo][eRev]; return new Edge { from = (int)(pos[idx] >> SHIFT_SIZE), to = eTo, cap = gCap[idxf][idxt] + reCap, flow = reCap }; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public Edge[] GetAllEdge() { var res = new Edge[posCnt]; for (var i = 0; i < res.Length; ++i) res[i] = GetEdge(i); return res; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void ChangeEdge(long i, long newCap, long newFlow) { var idx = (int)i; var idxf = pos[idx] >> SHIFT_SIZE; var idxt = (int)(pos[idx] & MASK); gCap[idxf][idxt] = newCap - newFlow; gCap[gTo[idxf][idxt]][gRev[idxf][idxt]] = newFlow; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public long Flow(long s, long t) => Flow(s, t, long.MaxValue >> 2); [MethodImpl(MethodImplOptions.AggressiveOptimization)] public long Flow(long s, long t, long flowLimit) { int si = (int)s; int ti = (int)t; var level = new int[N]; var iter = new int[N]; ref var iterref = ref iter[0]; Func dfs = null; dfs = (v, up) => { var res = 0L; ref var levelref = ref level[0]; ref var gToVref = ref gTo[v][0]; ref var gCapref = ref gCap[0]; ref var gCapVref = ref gCap[v][0]; ref var gRevVref = ref gRev[v][0]; var levelv = Unsafe.Add(ref levelref, v); ref var iterv = ref iter[v]; var gToCntV = gToCnt[v]; for (; iterv < gToCntV; ++iterv) { var gToVi = Unsafe.Add(ref gToVref, iterv); var gRevVi = Unsafe.Add(ref gRevVref, iterv); var gcap = Unsafe.Add(ref gCapref, gToVi)[gRevVi]; if (levelv <= Unsafe.Add(ref levelref, gToVi) || gcap == 0) continue; var param = Math.Min(up - res, gcap); var d = gToVi == si ? param : dfs(gToVi, param); if (d <= 0) continue; Unsafe.Add(ref gCapVref, iterv) += d; Unsafe.Add(ref gCapref, gToVi)[gRevVi] -= d; res += d; if (res == up) break; } return res; }; var flow = 0L; ref var levelref = ref level[0]; var que = new Queue(); while (flow < flowLimit) { Unsafe.InitBlock(ref Unsafe.As(ref levelref), 255, (uint)N << 2); Unsafe.Add(ref levelref, si) = 0; que.Enqueue(si); while (que.Count > 0) { var v = que.Dequeue(); ref var gToVref = ref gTo[v][0]; ref var gCapVref = ref gCap[v][0]; var levelv = Unsafe.Add(ref levelref, v) + 1; for (var i = 0; i < gToCnt[v]; ++i) { var gToVi = Unsafe.Add(ref gToVref, i); if (Unsafe.Add(ref gCapVref, i) == 0 || Unsafe.Add(ref levelref, gToVi) >= 0) continue; Unsafe.Add(ref levelref, gToVi) = levelv; if (gToVi == ti) { que.Clear(); break; } que.Enqueue(gToVi); } } if (Unsafe.Add(ref levelref, ti) == -1) break; Unsafe.InitBlock(ref Unsafe.As(ref iterref), 0, (uint)N << 2); while (flow < flowLimit) { var f = ti == si ? (flowLimit - flow) : dfs(ti, flowLimit - flow); if (f == 0) break; flow += f; } } return flow; } [MethodImpl(MethodImplOptions.AggressiveOptimization)] public bool[] MinCut(long s) { var visited = new bool[N]; var que = new Queue(); que.Enqueue((int)s); while (que.Count > 0) { var p = que.Dequeue(); visited[p] = true; var gToP = gTo[p]; var gCapP = gCap[p]; for (var i = 0; i < gToCnt[p]; ++i) { var gToPi = gToP[i]; if (gCapP[i] > 0 && !visited[gToPi]) { visited[gToPi] = true; que.Enqueue(gToPi); } } } return visited; } } class LIB_FastIO { [MethodImpl(MethodImplOptions.AggressiveInlining)] public LIB_FastIO() { str = Console.OpenStandardInput(); } readonly Stream str; readonly byte[] buf = new byte[2048]; int len, ptr; [MethodImpl(MethodImplOptions.AggressiveInlining)] byte read() { if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 2048)) <= 0) { return 0; } } return buf[ptr++]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] char Char() { byte b = 0; do b = read(); while (b < 33 || 126 < b); return (char)b; } [MethodImpl(MethodImplOptions.AggressiveInlining)] virtual public string Scan() { var sb = new StringBuilder(); for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b); return sb.ToString(); } [MethodImpl(MethodImplOptions.AggressiveInlining)] virtual public long Long() { long ret = 0; byte b = 0; var ng = false; do b = read(); while (b != '-' && (b < '0' || '9' < b)); if (b == '-') { ng = true; b = read(); } for (; true; b = read()) { if (b < '0' || '9' < b) return ng ? -ret : ret; else ret = (ret << 3) + (ret << 1) + b - '0'; } } [MethodImpl(MethodImplOptions.AggressiveInlining)] virtual public double Double() { return double.Parse(Scan(), CultureInfo.InvariantCulture); } } class LIB_FastIODebug : LIB_FastIO { Queue param = new Queue(); [MethodImpl(MethodImplOptions.AggressiveInlining)] string NextString() { if (param.Count == 0) foreach (var item in Console.ReadLine().Split(' ')) param.Enqueue(item); return param.Dequeue(); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public LIB_FastIODebug() { } [MethodImpl(MethodImplOptions.AggressiveInlining)] public override string Scan() => NextString(); [MethodImpl(MethodImplOptions.AggressiveInlining)] public override long Long() => long.Parse(NextString()); [MethodImpl(MethodImplOptions.AggressiveInlining)] public override double Double() => double.Parse(NextString()); } }