【题目描述】：
     现在，保密成为一个很重要也很困难的问题。如果没有做好，后果是严重的。比如，有个人没有自己去修电脑，又没有拆硬盘，后来的事大家都知道了。
     当然，对保密最需求的当然是军方，其次才是像那个人。为了应付现在天上飞来飞去的卫星，军事基地一般都会建造在地下。
     某K国的军事基地是这样子的：地面上两排大天井共n1个作为出入口，内部是许多除可以共享出入口外互不连通的空腔，每个空腔有且只有两个出入口，并且这两个出入口不会在同一排。为了方便起见，两排出入口分别编号为1,3,5…和2,4,6…并且最大的编号为n1。
      虽然上面扯了那么多关于保密的东西，但是其实解密也是一件很纠结的事情。但其实最简单直接暴力无脑的解密方法就是找个人去看看。。。
      我们有很牛X的特种部队，只需要派出一支特种部队到K国基地的某个出入口，那么和这个出入口直接相连的所有空腔都可以被探索，但也只有这些空腔可以被这支部队探索。现在有足够多的特种部队可以供你调遣，你必须使用他们调查完所有的K国基地内的空腔。
      当然，你的基地离K国基地不会太近，周边的地图将会给你，表示为n个检查点和m条连接这些点的道路，其中点1到点n1就是K国基地的出入口，点n是你的部队的出发点。对每条道路，有不同的通行时间t和安全系数s。因为情报部门只对单向的道路安全系数进行了评估，所以这些道路只允许单向通行，并且不会存在环。
      一支特种部队从你的基地出发，通过某条路径，到达某个K国基地出入口，此时这支部队的危险性表示为总时间和这条路径经过的所有道路的安全系数和的比值。整个行动的危险性表示为你派出的所有部队的危险性之和。你需要使这个值最小的情况下探索整个K国基地。
      快点完成这个任务，在K国的叫兽宣布你是K国人之前。
【题目解法】：
    《几个算法拼凑起来系列》
    瞄了一眼题解，貌似用了分数规划TAT
    出题人你真萌，既然要分数规划干嘛不把边权发大一点，你给个t<=10摆明暴力上啦
    我们用dis[i][j]表示到达i点安全系数为j时最小的时间，1<=i<=n 1<=j<=n*10
    spfa一发即可
    然后处理处dist[i]表示到达i点最小的比值
    对于奇数i，连边(s,i,dist[i])
    对于偶数i，连边(i,t,dist[i])
    对于某一个空腔u，它的两个出入口x y，连边(x,u,INF) (u,v,INF)
    然后最小割即可
    脑补了一下分数规划sigma(t[i])/sigma(s[i])=aim最小
    假设当前找到的最优解为now，令边权为t[i]-s[i]*now，然后跑最短路dist
    如果dist<0说明sigma(t[i])-sigma(s[i])*now<0 => sigma(t[i])/sigma(s[i])<now，说明存在比now更有的解
    二分或者迭代即可

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=705;
const int M=100005;
const double INF=1e15;
int n,m,n1,m1,S,T; double ans;
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
namespace NetWork
{
    const int N=50005;
    struct edge {int x,next,op; double y;} b[M*8];
    int tot,a[N],gap[N],cur[N],dis[N],pre[N],now;
    inline void addedge(int x,int y,double z)
    {
        ++tot; b[tot].x=y; b[tot].y=z; b[tot].op=tot+1; b[tot].next=a[x]; a[x]=tot;
        ++tot; b[tot].x=x; b[tot].y=0; b[tot].op=tot-1; b[tot].next=a[y]; a[y]=tot;
    }
    inline void init()
    {
        tot=0; memset(a,0,sizeof(a));
        S=0; T=n1+m1+1; ans=0;
    }
    inline void augment(int s,int t)
    {
        double flow=INF;
        for (int i=s; i!=t; i=b[cur[i]].x) flow=min(flow,b[cur[i]].y);
        for (int i=s; i!=t; i=b[cur[i]].x) b[cur[i]].y-=flow,b[b[cur[i]].op].y+=flow;
        ans+=flow; now=s;
    }
    void Sap(int s,int t)
    {
        for (int i=S; i<=T; i++) cur[i]=a[i],gap[i]=0,pre[i]=0,dis[i]=0;
        now=s; gap[t]=T; ans=0;
        while (dis[s]<=T)
        {
            if (ans>=INF) return;
            if (now==t) augment(s,t); bool Flag=false;
            for (int p=cur[now];p;p=b[p].next)
            {
                int pp=b[p].x; if ((b[p].y<=0)||(dis[pp]+1!=dis[now])) continue;
                pre[pp]=now; cur[now]=p; Flag=true; now=pp; break;
            }
            if (Flag) continue; cur[now]=a[now];
            gap[dis[now]]--; if (gap[dis[now]]==0) break; dis[now]=T+1;
            for (int p=cur[now];p;p=b[p].next)
            {
                int pp=b[p].x;
                if (b[p].y>0) dis[now]=min(dis[now],dis[pp]+1);
            }
            gap[dis[now]]++; if (now!=s) now=pre[now];
        }
    }
}
namespace Graph
{
    const int Size=2000005;
    struct edge {int x,s,t,next;} b[M];
    struct node {int x,y;} q[Size];
    int tot,a[N],dis[N][N*10]; bool v[N][N*10]; double dist[N];
    inline void addedge(int x,int y,int s,int t)
    {
        ++tot;
        b[tot].x=y;
        b[tot].s=s;
        b[tot].t=t;
        b[tot].next=a[x];
        a[x]=tot;
    }
    void init()
    {
        n=getint(); m=getint(); tot=0;
        memset(a,0,sizeof(a));
        for (int i=1; i<=m; i++)
        {
            int x=getint(),y=getint(),s=getint(),t=getint();
            addedge(x,y,s,t);
        }
    }
    void spfa()
    {
        memset(dis,127,sizeof(dis)); dis[n][0]=0;
        int head=0,tail=1; q[1].x=n; q[1].y=0; v[n][0]=true;
        for (int i=1; i<=n; i++) dist[i]=INF; dist[n]=n;
        while (head<tail)
        {
            ++head; if (head>=Size) head=1;
            int x=q[head].x,y=q[head].y; v[x][y]=false;
            if (y!=0) dist[x]=min(dist[x],(double)dis[x][y]/y);
            for (int p=a[x];p;p=b[p].next)
            {
                int X=b[p].x,Y=y+b[p].t;
                if (dis[x][y]+b[p].s>=dis[X][Y]) continue;
                dis[X][Y]=dis[x][y]+b[p].s; if (v[X][Y]) continue;
                ++tail; if (tail>=Size) tail=1; q[tail].x=X; q[tail].y=Y; v[X][Y]=true;
            }
        }
    }
    void build()
    {
        m1=getint(); n1=getint(); NetWork::init();
        for (int i=1; i<=n1; i++)
        {
            if (i%2==1) NetWork::addedge(S,i,dist[i]);
            if (i%2==0) NetWork::addedge(i,T,dist[i]);
        }
        for (int i=1; i<=m1; i++)
        {
            int x=getint(),y=getint();
            NetWork::addedge(x,i+n1,INF);
            NetWork::addedge(i+n1,y,INF);
        }
    }
}
void solve()
{
    if (ans>=INF) printf("-1\n");
    else printf("%.1lf\n",ans);
}
int main()
{
    Graph::init();
    Graph::spfa();
    Graph::build();
    NetWork::Sap(S,T);
    solve();
    return 0;
}