Sachverhalt:
A.
Am 16. August 2012 erteilte der Gemeindevorstand Vals C.Y._ und D.Y._ die Baubewilligung für ein Wohnhaus auf dem Grundstück Nr. 956 im Gebiet "Leis" mit Auflagen. Gleichzeitig wies es die gegen das Bauvorhaben erhobene Einsprache von A.X._ und B.X._ im Sinne der Erwägungen ab.
Die Gemeinde führte aus, das Gebiet "Leis" sei eine autofreie Zone; die Grundeigentümer parkierten auf einer von der Gemeinde zur Verfügung gestellten Parkzone ausserhalb des Gebiets. Allerdings müssten die Baugesuchsteller die Möglichkeit haben, zu Fuss zu ihrem Grundstück zu gelangen, damit das Grundstück als erschlossen erachtet werden könne. Der bestehende Feldweg führe über mehrere private Grundstücke. Zur Nutzung dieses Weges sei deshalb die Zustimmung der Eigentümer erforderlich, respektive müsse die Nutzung durch privatrechtliche Vereinbarungen gesichert sein. Die Baubewilligung wurde daher mit der Bedingung verknüpft, dass die Baufreigabe erst erfolge, nachdem die erforderlichen schriftlichen zivilrechtlichen Vereinbarungen vorlägen. Diese hätten sich sowohl auf ein Fusswegrecht als auch auf ein Fahrwegrecht für die Bauphase und den Gebäudeunterhalt zu beziehen. Die Baubewilligung erlösche, wenn die geforderten Vereinbarungen nicht innert eines Jahres seit Rechtskraft der Verfügung eingereicht werden.
B.
Gegen den Einspracheentscheid sowie die Baubewilligung erhoben A.X._ und B.X._ am 24. September 2012 Beschwerde beim Verwaltungsgericht des Kantons Graubünden mit der Begründung, es liege keine genügende strassenmässige Erschliessung des Baugrundstücks vor. Das Verwaltungsgericht bejahte eine rechtsgenügliche Erschliessung und wies die Beschwerde am 27. November 2012 ab.
C.
Dagegen haben A.X._ und B.X._ am 28. Januar 2013 Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht erhoben. Sie beantragen, der angefochtene Entscheid und die Baubewilligung seien aufzuheben und das Baugesuch abzuweisen. In ihrer Beschwerdebegründung berufen sie sich erstmals auf die Verletzung von <ref-law> und <ref-law>.
D.
C.Y._ und D.Y._ (im Folgenden: die Beschwerdegegner) sowie die Gemeinde Vals schliessen auf Abweisung der Beschwerde. Das Verwaltungsgericht beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei.
Die Beschwerdegegner machen geltend, dass die Zweitwohnungsnutzung weder im Einspracheverfahren noch vor Verwaltungsgericht thematisiert worden sei. Das Vorbringen, das Bauvorhaben verstosse gegen <ref-law>, sei daher ein unzulässiges Novum (<ref-law>). Die Baubewilligung sei in diesem Punkt nicht angefochten und damit rechtskräftig geworden. Für den Fall, dass das Bundesgericht dennoch auf diese Rüge eintreten sollte, beantragen die Beschwerdegegner eventualiter, die Baubewilligung sei zu bestätigen und das Grundbuchamt Vals sei gestützt auf Art. 6 der Verordnung über Zweitwohnungen vom 22. August 2012 (SR 702) anzuweisen, auf dem Grundbuchblatt des Grundstücks Nr. 956 die Anmerkung "Erstwohnung" oder "bewirtschaftete Zweitwohnung" einzutragen.
E.
Mit Verfügung vom 20. Februar 2013 wurde das Gesuch um Gewährung der aufschiebenden Wirkung abgewiesen.

Erwägungen:
1.
Gegen den kantonal letztinstanzlichen Endentscheid des Verwaltungsgerichts steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht offen (Art. 82 lit. a und 86 Abs. 1 lit. d BGG). Die Beschwerdeführer sind als unmittelbare Nachbarn zur Beschwerde legitimiert (<ref-law>). Auf die rechtzeitig erhobene Beschwerde (<ref-law>) ist daher einzutreten.
2.
Der Streitgegenstand bestimmt sich aufgrund des Anfechtungsobjekts (d.h. des Dispositivs des vorinstanzlichen Entscheids) und der gestellten Anträge (<ref-ruling> E. 3.4.3 S. 365; <ref-ruling> E. 2 S. 415 ff.; je mit Hinweisen). Vorliegend wurde die von den Beschwerdeführern vollumfänglich angefochtene Baubewilligung vom Verwaltungsgericht (durch Abweisung der Beschwerde) bestätigt; auch vor Bundesgericht beantragen die Beschwerdeführer die Aufhebung der Baubewilligung und die Abweisung des Baugesuchs. Im Streit steht somit die Bewilligungsfähigkeit des Bauvorhabens als Ganzes. Einzelne Teilaspekte davon stellen Begründungselemente dar, die für sich allein nicht in Rechtskraft erwachsen ( ULRICH MEYER/ISABEL VON ZWEHL, L'objet du litige en procédure de droit administratif fédéral, Mélanges Pierre Moor, 2005, S. 435 ff., S. 441 ff.). Insofern ist die Baubewilligung nicht - wie die Beschwerdegegner meinen - in Bezug auf die Zweitwohnungsproblematik in Rechtskraft erwachsen.
Neue rechtliche Begründungen sind vor Bundesgericht grundsätzlich zulässig (<ref-ruling> E. 4.1 S. 366 mit Hinweisen). Ohnehin kann dieses die Vereinbarkeit der Baubewilligung mit Art. 75b i.V.m. <ref-law> von Amtes wegen prüfen (<ref-law>). Zwar legt es seinem Urteil grundsätzlich den vorinstanzlich festgestellten Sachverhalt zugrunde (<ref-law>); es kann aber ausnahmsweise auch selber eine Sachverhaltsfeststellung ergänzen (<ref-law>), namentlich dann, wenn ein Sachverhaltselement erst infolge einer anderen rechtlichen Betrachtung des Bundesgerichts rechtserheblich wird (<ref-ruling> E. 4.1 S. 366).
3.
Das Bundesgericht hat in <ref-ruling> E. 9-11 S. 249 ff. entschieden, dass <ref-law> seit seinem Inkrafttreten am 11. März 2012 anwendbar ist. Zwar bedarf diese Bestimmung in weiten Teilen der Ausführung durch ein Bundesgesetz. Unmittelbar anwendbar ist sie jedoch insoweit, als sie (in Verbindung mit <ref-law>) ein Baubewilligungsverbot für Zweitwohnungen in allen Gemeinden anordnet, in denen der 20 %-Zweitwohnungsanteil bereits erreicht oder überschritten ist. Dies hat zur Folge, dass Baubewilligungen für Zweitwohnungen, die zwischen dem 11. März und dem 31. Dezember 2012 in den betroffenen Gemeinden erteilt wurden, auf entsprechende Beschwerde hin aufzuheben sind.
Vorliegend wurde die Baubewilligung am 16. August 2012, d.h. nach dem Inkrafttreten von <ref-law> und <ref-law>, erteilt. Es ist unstreitig, dass der Zweitwohnungsanteil der Gemeinde Vals über 20 % beträgt (vgl. auch Anh. zur Zweitwohnungsverordnung, Gemeinde Nr. 3603).
Sowohl die Gemeinde als auch das Verwaltungsgericht gingen davon aus, dass der Neubau als Zweitwohnung genutzt werden solle (vgl. Sachverhalt S. 10 unten und E. 3b S. 13 des angefochtenen Entscheids). Die Baubewilligung enthält keine Nutzungsbeschränkung und lässt somit eine Zweitwohnungsnutzung zu. Sie verstösst daher gegen <ref-law> i.V.m. <ref-law> und ist aufzuheben.
4.
Ob das Bauvorhaben mit einer Nutzungsbeschränkung als Erstwohnung oder als qualifiziert bewirtschaftete Zweitwohnung i.S.v. Art. 4 lit. b Ziff. 1 Zweitwohnungsverordnung bewilligt werden könnte, ist nicht erstmals im bundesgerichtlichen Verfahren zu prüfen. Es ist in diesem Zusammenhang lediglich darauf hinzuweisen, dass beide Nutzungsarten an bestimmte Voraussetzungen gebunden sind und auch geprüft werden müsste, ob sie erhöhte Anforderungen an die Erschliessung der Bauparzelle stellen.
5.
Unter diesen Umständen rechtfertigt es sich, nicht nur den verwaltungsgerichtlichen Entscheid, sondern auch den Bau- und Einspracheentscheid sowie die Baubewilligung aufzuheben und die Sache an die Gemeinde zurückzuweisen. Wollen die Beschwerdegegner an ihrem Bauvorhaben festhalten, müssen sie das Baugesuch mit den nötigen Angaben ergänzen. Zudem müsste den Beschwerdeführern im Einspracheverfahren das rechtliche Gehör gewährt werden. Verzichten sie dagegen auf das Baugesuch, kann die Gemeinde einen Abschreibungsbeschluss erlassen und darin auch die Kosten des Bauverfahrens neu verlegen.
Bei diesem Ausgang des Verfahrens obsiegen die Beschwerdeführer. Die Beschwerdegegner werden kostenpflichtig, und zwar sowohl für das bundesgerichtliche Verfahren (Art. 66 und 68 BGG) als auch für das Verfahren vor Verwaltungsgericht (Art. 67 und 68 Abs. 5 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen und der Entscheid des Verwaltungsgerichts des Kantons Graubünden, 5. Kammer, vom 27. November 2012, sowie der Einspracheentscheid und die Baubewilligung der Gemeinde Vals vom 16. August 2012 werden aufgehoben. Die Sache wird im Sinne der Erwägungen an die Gemeinde Vals zurückgewiesen.
2.
Die Gerichtskosten von Fr. 3'000.-- für das bundesgerichtliche Verfahren und Fr. 3'428.-- für das verwaltungsgerichtliche Verfahren werden den Beschwerdegegnern (C.Y._ und D.Y._) auferlegt.
3.
Die Beschwerdegegner haben die Beschwerdeführer für das bundesgerichtliche und für das verwaltungsgerichtliche Verfahren mit insgesamt Fr. 5'000.-- (je Fr. 2'500.--) zu entschädigen.
4.
Dieses Urteil wird den Parteien, der Gemeinde Vals und dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, schriftlich mitgeteilt.
Lausanne, 4. Oktober 2013
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Die Gerichtsschreiberin: Gerber