来自"NOCOW"

---

Solution From WX

题目大意：

给出一个联通无向图，
要求为M条边用1--M标号，
使得与每个顶点相邻的边的最大公约数为1。

解题思路：

KISS。。。
最大公约数为1-->其中一个数为1 或 
                有两数互质-->有两数相邻-->DFS？？？

算法：

1.DFS遍历整个图，同时为每条边按发现顺序标号；
2.一定有解，于是输出"YES"及answer。。。

证明：

无向图-->DFS中只存在树边与后向边；
连通图-->一次DFS搞定；
a.对于根节点，
  有一条临边标号为1；
b.对于每个非根且度大于1的节点i，
  若与他父亲节点par[i]相连的边标号为k，
  则必有另一条与之相邻的边标号为k+1；
c.对于每个非根且度为1的节点。。。不用理他啦！！！

My Code:

program wx;
  var i,j,k,m,n,p,q:longint;
      a:array[1..1000,1..1000]of boolean;
      d:array[1..1000,1..1000]of longint;
      s:array[1..1000000,1..2]of longint;
      f:array[1..1000]of boolean;
  procedure dfs(x:longint);
    var i:longint;
    begin
      f[x]:=true;
      for i:=1 to n do
        if a[x,i] and(d[x,i]=0) then
          begin
            inc(k);
            d[x,i]:=k;
            d[i,x]:=k;
            if not f[i] then dfs(i);
          end;
    end;
  begin
    readln(n,m);
    for i:=1 to m do
      begin
        readln(p,q);
        s[i,1]:=p;s[i,2]:=q;
        a[p,q]:=true;
        a[q,p]:=true;
      end;
    dfs(1);
    writeln('YES');
    for i:=1 to m-1 do
      write(d[s[i,1],s[i,2]],' ');
    writeln(d[s[m,1],s[m,2]]);
  end.

---

Solution From Xcheng

求DFS序列，依次对边用1~M编号。

---

诡异的贪心，方法就是dfs的时候把经过的边按1..n编号，保证这样的边数字相邻从而互质，然后判断所有的点是否满足情况，如果这样不满足情况就不行（原因不详），否则就输出这样的编号。

Solution From ZongZi

---

题目要求与每个顶点相连的所有边编号最大公约数为1，其实只要其中的两条边编号互质，所有边编号的最大公约数一定为1。我们知道相邻的数字一定互质，那么只要与一个顶点相连的所有边中有两条编号相邻，这个顶点就可以符合条件。DFS序列，对边进行编号刚好可以构造出满足要求的解，并且无解的情况是不存在的。