{"raw_statement":[{"iden":"statement","content":"Oleg the bank client lives in Bankopolia. There are _n_ cities in Bankopolia and some pair of cities are connected directly by bi-directional roads. The cities are numbered from 1 to _n_. There are a total of _m_ roads in Bankopolia, the _i_\\-th road connects cities _u__i_ and _v__i_. It is guaranteed that from each city it is possible to travel to any other city using some of the roads.\n\nOleg wants to give a label to each city. Suppose the label of city _i_ is equal to _x__i_. Then, it must hold that for all pairs of cities (_u_, _v_) the condition |_x__u_ - _x__v_| ≤ 1 holds if and only if there is a road connecting _u_ and _v_.\n\nOleg wonders if such a labeling is possible. Find an example of such labeling if the task is possible and state that it is impossible otherwise."},{"iden":"input","content":"The first line of input contains two space-separated integers _n_ and _m_ (2 ≤ _n_ ≤ 3·105, 1 ≤ _m_ ≤ 3·105) — the number of cities and the number of roads.\n\nNext, _m_ lines follow. The _i_\\-th line contains two space-separated integers _u__i_ and _v__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_, _u__i_ ≠ _v__i_) — the cities connected by the _i_\\-th road. It is guaranteed that there is at most one road between each pair of cities and it is possible to travel from any city to any other city using some roads."},{"iden":"output","content":"If the required labeling is not possible, output a single line containing the string \"_NO_\" (without quotes).\n\nOtherwise, output the string \"_YES_\" (without quotes) on the first line. On the next line, output _n_ space-separated integers, _x_1, _x_2, ..., _x__n_. The condition 1 ≤ _x__i_ ≤ 109 must hold for all _i_, and for all pairs of cities (_u_, _v_) the condition |_x__u_ - _x__v_| ≤ 1 must hold if and only if there is a road connecting _u_ and _v_."},{"iden":"examples","content":"Input\n\n4 4\n1 2\n1 3\n1 4\n3 4\n\nOutput\n\nYES\n2 3 1 1 \n\nInput\n\n5 10\n1 2\n1 3\n1 4\n1 5\n2 3\n2 4\n2 5\n3 4\n3 5\n5 4\n\nOutput\n\nYES\n1 1 1 1 1 \n\nInput\n\n4 3\n1 2\n1 3\n1 4\n\nOutput\n\nNO"},{"iden":"note","content":"For the first sample, _x_1 = 2, _x_2 = 3, _x_3 = _x_4 = 1 is a valid labeling. Indeed, (3, 4), (1, 2), (1, 3), (1, 4) are the only pairs of cities with difference of labels not greater than 1, and these are precisely the roads of Bankopolia.\n\nFor the second sample, all pairs of cities have difference of labels not greater than 1 and all pairs of cities have a road connecting them.\n\nFor the last sample, it is impossible to construct a labeling satisfying the given constraints."}],"translated_statement":[{"iden":"statement","content":"Oleg 是 Bankopolia 的银行客户。Bankopolia 有 #cf_span[n] 座城市，其中一些城市对通过双向道路直接相连。城市编号从 #cf_span[1] 到 #cf_span[n]。Bankopolia 总共有 #cf_span[m] 条道路，第 #cf_span[i] 条道路连接城市 #cf_span[ui] 和 #cf_span[vi]。保证从任意一座城市都可以通过若干条道路到达其他任意城市。\n\nOleg 希望为每座城市赋予一个标签。假设城市 #cf_span[i] 的标签为 #cf_span[xi]，则必须满足：对于任意城市对 #cf_span[(u, v)]，条件 #cf_span[|xu - xv| ≤ 1] 成立当且仅当存在一条连接 #cf_span[u] 和 #cf_span[v] 的道路。\n\nOleg 想知道这样的标签分配是否可能。如果可能，请给出一个满足条件的标签分配方案；否则，说明不可能。\n\n输入的第一行包含两个空格分隔的整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 3·105]，#cf_span[1 ≤ m ≤ 3·105]），分别表示城市数量和道路数量。\n\n接下来 #cf_span[m] 行，每行包含两个空格分隔的整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n]，#cf_span[ui ≠ vi]），表示第 #cf_span[i] 条道路连接的两座城市。保证任意两座城市之间至多有一条道路，且任意两座城市之间均可通过若干条道路互相到达。\n\n如果无法构造满足要求的标签分配，请输出一行字符串 \"_NO_\"（不含引号）。\n\n否则，第一行输出字符串 \"_YES_\"（不含引号），第二行输出 #cf_span[n] 个空格分隔的整数 #cf_span[x1, x2, ..., xn]。要求对所有 #cf_span[i] 满足 #cf_span[1 ≤ xi ≤ 109]，且对任意城市对 #cf_span[(u, v)]，条件 #cf_span[|xu - xv| ≤ 1] 成立当且仅当存在一条连接 #cf_span[u] 和 #cf_span[v] 的道路。\n\n对于第一个样例，#cf_span[x1 = 2]，#cf_span[x2 = 3]，#cf_span[x3 = x4 = 1] 是一个合法的标签分配。确实，#cf_span[(3, 4)]、#cf_span[(1, 2)]、#cf_span[(1, 3)]、#cf_span[(1, 4)] 是唯一满足标签差值不超过 #cf_span[1] 的城市对，而这些恰好是 Bankopolia 的所有道路。\n\n对于第二个样例，所有城市对的标签差值都不超过 #cf_span[1]，且所有城市对之间都存在道路。\n\n对于最后一个样例，无法构造满足给定约束的标签分配。"},{"iden":"input","content":"输入的第一行包含两个空格分隔的整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 3·105]，#cf_span[1 ≤ m ≤ 3·105]），分别表示城市数量和道路数量。接下来 #cf_span[m] 行，每行包含两个空格分隔的整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n]，#cf_span[ui ≠ vi]），表示第 #cf_span[i] 条道路连接的两座城市。保证任意两座城市之间至多有一条道路，且任意两座城市之间均可通过若干条道路互相到达。"},{"iden":"output","content":"如果无法构造满足要求的标签分配，请输出一行字符串 \"_NO_\"（不含引号）。否则，第一行输出字符串 \"_YES_\"（不含引号），第二行输出 #cf_span[n] 个空格分隔的整数 #cf_span[x1, x2, ..., xn]。要求对所有 #cf_span[i] 满足 #cf_span[1 ≤ xi ≤ 109]，且对任意城市对 #cf_span[(u, v)]，条件 #cf_span[|xu - xv| ≤ 1] 成立当且仅当存在一条连接 #cf_span[u] 和 #cf_span[v] 的道路。"},{"iden":"examples","content":"输入\n4 4\n1 2\n1 3\n1 4\n3 4\n输出\nYES\n2 3 1 1\n\n输入\n5 10\n1 2\n1 3\n1 4\n1 5\n2 3\n2 4\n2 5\n3 4\n3 5\n5 4\n输出\nYES\n1 1 1 1 1\n\n输入\n4 3\n1 2\n1 3\n1 4\n输出\nNO"},{"iden":"note","content":"对于第一个样例，#cf_span[x1 = 2]，#cf_span[x2 = 3]，#cf_span[x3 = x4 = 1] 是一个合法的标签分配。确实，#cf_span[(3, 4)]、#cf_span[(1, 2)]、#cf_span[(1, 3)]、#cf_span[(1, 4)] 是唯一满足标签差值不超过 #cf_span[1] 的城市对，而这些恰好是 Bankopolia 的所有道路。对于第二个样例，所有城市对的标签差值都不超过 #cf_span[1]，且所有城市对之间都存在道路。对于最后一个样例，无法构造满足给定约束的标签分配。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with $ |V| = n $, $ |E| = m $, where $ V = \\{1, 2, \\dots, n\\} $ is the set of vertices (cities) and $ E \\subseteq \\binom{V}{2} $ is the set of edges (roads).  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 3 \\cdot 10^5 $  \n2. $ 1 \\leq m \\leq 3 \\cdot 10^5 $  \n3. $ G $ is connected.  \n4. For each edge $ (u, v) \\in E $, it holds that $ |x_u - x_v| \\leq 1 $.  \n5. For each non-edge $ (u, v) \\notin E $, it holds that $ |x_u - x_v| > 1 $.  \n6. Each label $ x_i \\in \\mathbb{Z} $, $ 1 \\leq x_i \\leq 10^9 $.  \n\n**Objective**  \nDetermine whether there exists a labeling $ x: V \\to \\mathbb{Z} $ satisfying conditions (4) and (5). If yes, output such a labeling; otherwise, output \"NO\".","simple_statement":null,"has_page_source":false}